The seminar is usually on Thursdays at 11:00 AM
The seminar will be followed by the Thursday Lunch Expedition.
Thursday December 4, 2008
Kyle Burke (Boston University)
Title: A Sperner Triangle Game
Kemeny 120 and TIME: 11:00 AM
Abstract: With the recent application of Sperner's Lemma to the complexity of
finding market Nash Equilibria, we are motivated to further explore
Sperner's Triangle. Taking a recreational path, we use this triangle to
create the board game Atropos. In this talk, we will describe many nice
properties of the game. After playing a test match against the audience,
we show that determining a winning strategy is a PSPACE-complete problem.
Google for 'Atropos Game' for a playable applet of the game.
Thursday November 20, 2008
Karola Meszaros (MIT)
Title: Understanding root polytopes via algebraic relations and vice versa
Kemeny 120 and TIME: 11:00 AM
Abstract: The type A_{n-1} root polytope is the convex hull in R^n of the origin and
points e_i-e_j for 1\leq i< j \leq n. We will discuss a connection between
triangulations of root polytopes and reduced forms of a monomial in an
algebra generated by n^2 variables x_{ij}, for 1\leq i< j \leq n. We show
that the reduced form is unique, and corresponds to a canonical
triangulation of the root polytope in which each simplex corresponds to a
noncrossing alternating tree.
Thursday November 6, 2008
Peter Winkler (Dartmouth College)
Title: The Pizza Problem
Kemeny 120 and TIME: 11:00 AM
Abstract: Alice and Bob share a pizza, radially cut into
slices of various sizes. Alice gets to pick any
slice to start. After that they alternate taking
slices, but must always take a slice which is adjacent
to some previously-taken slice. (This is called the
Polite Pizza Protocol.)
Is is possible that the pizza is cut in such a way
that no matter what Alice does, Bob can get more than half?
Thursday October 23, 2008
John Schmitt (Middlebury College)
Title: A dual to the Turan problem
Kemeny 120 and TIME: 11:00 AM
Abstract: A graph $G$ is $F$-saturated if $G$ contains no copy of $F$ and any proper
supergraph of $G$ does. Tur\'an introduced the problem of determining the
maximum number of edges of an $F$-saturated $n$-vertex graph. Here we
consider the dual problem, determining the minimum number of edges in an
$F$-saturated $n$-vertex graph. We present recent results for various
choices of $F$, survey known results, and give many open problems.
This is joint work with Ron Gould, Tomasz Luczak and Oleg Pikhurko.
Monday September 29, 2008
Thomas Prellberg (Queen Mary, University of London)
Title: Counting Defective Parking Functions
Kemeny 108 and TIME: 4:00 PM
Abstract: Suppose that n drivers each choose a preferred parking space in a linear car
park with m spaces. Each driver goes to the chosen space and parks there if it
is free, and otherwise takes the first available space
with larger number (if any).
If all drivers park successfully, the sequence of choices is called a parking
function. In general, if k drivers fail to park, we have a defective parking
function of defect k. Let cp(n,m,k) be the number of
such functions.
In this talk, we establish a recurrence relation for the cp(n,m,k), and express
this as an equation for a three-variable generating function. We solve this
equation using the kernel method, and extract the
coefficients explicitly: it turns out that the cumulative totals are partial
sums in Abel's binomial identity. Finally, we compute the asymptotics of
cp(n,m,k) in interesting limiting cases.
Thursday, September 18 2008
Graham Brightwell (London School of Economics)
Title: Random Natural Extensions of Causal Sets
Abstract: A causal set is a countably infinite labelled poset in which every element
is above finitely many others. A natural extension of a causal set is an
order-preserving bijection from the causal set to the set of natural
numbers.
We are interested in random processes that generate a causal set, one
element at a time. Alternatively, we are interested in random processes
that generate a natural extension of a given causal set, again one element
at a time. These two notions can be incorporated into a single framework.
The talk will focus on some of the interesting probabilistic and
combinatorial aspects of the work. I will also mention some connections
to the theory of Gibbs measures, and to models of the space-time universe.
This is joint work with Malwina Luczak.
Wednesday, September 10, 2008
Bruce Sagan (NSF and Michigan State University)
Title: Infinite log-concavity
Abstract:
Let $(a_k)=a_0,a_1,a_2,\ldots$ be a sequence of real numbers. For
convenience, we let $a_k=0$ if $k<0$. The sequence is {\it log-concave\/} if
$a_k^2\ge a_{k-1}a_{k+1}$ for all $k$. Log-concave sequences frequently
appear in algebra, combinatorics, and geometry. Define the {\it
$\cL$-operator\/} on sequences by $\cL(a_k)=(b_k)$ where
$$
b_k=a_k^2-a_{k-1}a_{k+1}.
$$
So $(a_k)$ is log-concave if and only if $\cL(a_k)$ is a nonnegative
sequence. Define $(a_k)$ to be {\it infinitely log-concave\/} if
$\cL^i(a_k)$ is nonnegative for all $i\ge1$.
Boros and Moll conjectured that
the sequence of binomial coefficients
$$
{n\choose0}, {n\choose1}, {n\choose2},\ldots
$$
is infinitely log-concave for any $n\ge0$.
We prove that this conjecture is true for all $n\le 1450$ by using a computer and a
stronger version of log-concavity. We also discuss infinite log-concavity of
the columns of Pascal's triangle, $q$-analogues, symmetric functions,
real-rooted polynomials, and Toeplitz matrices. There will be many
conjectures sprinkled throughout the lecture.
This is joint work with Peter R. W. McNamara.
If you are intenterested in speaking please email Rosa.C.Orellana "at" Dartmouth "dot" edu
or Sergi Elizalde
This
page is maintained by Rosa
Orellana