Combinatorics Seminar

Fall 2008

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