Richard P. Stanley Seminar in Combinatorics

Triangulations of a convex polygon are known to be counted by the Catalan numbers. A natural generalization of a triangulation is a $k$-triangulation, which is defined to be a maximal set of diagonals so that no $k+1$ of them mutually cross in their interiors. It was proved by Jakob Jonsson that $k$-triangulations are enumerated by certain determinants of Catalan numbers, that are also known to count $k$-tuples of non-crossing Dyck paths.

There are several simple bijections between triangulations of a convex $n$-gon and Dyck paths. However, no bijective proof of Jonsson's result is known for general $k$. In this talk I will give a bijective proof for the case $k=2$, that is, I will present a bijection between $2$-triangulations of a convex $n$-gon and pairs $(P,Q)$ of Dyck paths of semilength $n-4$ so that $P$ never goes below $Q$. The bijection is obtained by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.

In this talk we will introduce some combinatorial objects motivated by the Schubert calculus of the affine Grassmannian.

We give "affine" generalizations of the notions of semistandard Young tableaux and the RSK (Robinson-Schensted Knuth) algorithm. Our affine tableaux come in two versions, a weak and a strong one. Weak and strong tableaux are certain chains in the weak and strong (Bruhat) orders of the affine symmetric group respectively.

Our main result is an affine insertion algorithm, generalizing the RSK algorithm, which sends matrices to pairs (P,Q) of a strong tableau P and a weak tableau Q of the same shape. As a special case, we find that the weak order and strong order (labeled by affine Chevalley coefficients) of the affine symmetric group forms a pair of dual graded graphs in the sense of Fomin.

While our work is geometrically motivated, no knowledge of geometry will be assumed. This is joint work with Lapointe, Morse and Shimozono

A Littlewood-Richardson rule is a positive rule for computing the structure constants of the cohomology ring of flag varieties with respect to their Schubert basis. In recent years new geometric Littlewood-Richardson rules have led to the solution of many important problems, including Knutson and Tao's solution of Horn's conjecture and Vakil's solution of the reality of Schubert calculus. In this talk I will survey some of the basic geometric ideas that underlie these new Littlewood-Richardson rules.

A matching in a graph is a set of edges such that no two edges in the set have a vertex in common. The matching complex $M_n$ is the simplicial complex of matchings in the complete graph $K_n$. Bouc provided a complete description of the rational homology of $M_n$, but the integral homology remains a mystery in general. We will give an overview of known properties of this homology and also present some open problems and conjectures.

Introduced by J. Pearl to model conditional independence and useful in statistical learning theory, a semigraphoid is a collection of conditional independence statements i,j|K subject to certain axioms. I will show using a result of Tits that semigraphoids are equivalent to coarsenings of the braid arrangement, and relate them to poset arrangements and generalized permutohedra. Nice classes of these objects include those arising from submodular functions as certain regular subdivisions of the n-cube, and graph associahedra, which correspond to graphical models in statistics. The geometric point of view on semigraphoids, together with a toric algebraic perspective, is exploited to find counterexamples to conjectures of Studeny and a question of Postnikov, Reiner, and Williams.

In 1944 Freeman Dyson proposed the existence of a crank function that would combinatorially explain the Ramanujan congruences for the partition function. Dyson's call wasn't answered until 1987, when Garvan and Andrews devised a combinatorial interpretation of some interesting $q$-series in Ramanujan's "Lost Notebook", and showed that this statistic decomposed the three congruences in a natural way. However, in 2000 Ono revolutionized the subject by proving the existence of infinite families of congruences, again raising the question of finding combinatorial explanations for the new congruences. The present work shows that the crank continues to act as a sort of "universal" statistic for partition congruences, and satisfies exactly the same general congruence properties as the partition function.

We prove an upper bound, sharp up to a factor of 2, for the number of vertices of level at most $\ell$ in an arrangement of $n$ halfspaces in $\mathbb R^d$, for arbitrary $n$ and $d$ (in particular, the dimension $d$ is not considered constant). This partially settles a conjecture due to Eckhoff, Linhart, and Welzl.

Up to the factor of 2, the result generalizes McMullen's Upper Bound Theorem for convex polytopes (the case $\ell=0$) and extends a theorem of Linhart for the case $d \leq 4$. Moreover, the bound sharpens asymptotic estimates obtained by Clarkson and Shor.

The proof is based on the $h$-matrix of the arrangement (a generalization, introduced by Mulmuley, of the $h$-vector of a convex polytope). We show that bounding appropriate sums of entries of this matrix reduces to a lemma about quadrupels of sets with certain intersection properties, and we prove this lemma, up to a factor of 2, using tools from multilinear algebra. This extends an approach of Alon and Kalai, who used a similar lemma for pairs of sets to give an alternative proof of the classical Upper Bound Theorem.

The bounds for the entries of the $h$-matrix also imply bounds for the number of $i$-dimensional faces, $i>0$, at level at most $\ell$ but in general these are less satisfying than in the case $\ell=0$.

I will survey a class of problems with the following general theme: Given a set of N overlapping geometric objects, such as disks or squares, in the plane, consider their union. A vertex on the boundary of the union is a point where boundaries of two objects meet. The complexity of the union is the number of vertices on its boundary. Let $c(N)$ be maximum such complexity, over all possible choices of N objects. We are interested in asymptotic behavior of $c(N)$ as a function of N, for a variety of object classes, in two and higher dimensions.

Investigation of these functions has connections to geometric algorithms on the one hand and to a variety of geometric, combinatorial, and topological questions on the other.

In 1978, Uffe Haagerup proved an important inequality relating two functional analytic norms (the $\ell^2$-norm and the convolution norm) on the group algebra of a free group. While invented to be used in operator algebras, the inequality also found important uses in geometric group theory, probability theory, and other fields.

From a combinatorial standpoint, one can analyze the above-mentioned norms in terms of {\em free cumulants} associated to elements in the free group. Free cumulants are multilinear functions defined using M\"obius inversion on the lattice of non-crossing partitions $NC$.

In this talk, I will discuss recent work on a surprisingly strong improvement of Haagerup's inequality, which extends far beyond the context of the free group. The results rely fundamentally on the structure of $NC$.

A working knowledge of partitions and basic combinatorial constructions such as M\"obius inversion will be an asset, but {\em no knowledge of functional analysis} will be assumed.

Erd\'elyi's work on multivariate hypergeometric functions in the 1950's raises fundamental questions about the number of holomorphic solutions to classical Horn systems. Techniques developed by Gelfand, Kapranov, Zelevinsky, and others in the 1980's and 1990's successfully deal with series solutions having full support (where the set of monomials with nonzero coefficients fills a cone of the maximum possible dimension). In work with Alicia Dickenstein and Laura Matusevich, we show that dealing with all holomorphic solutions is intimately tied to precise combinatorial descriptions, in terms of lattice points, of primary components of binomial ideals in polynomial rings. The talk will paint a more detailed picture of the historical development as well as the recent advances.

The partially asymmetric exclusion process (PASEP) is an important model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice of N sites. It is partially asymmetric in the sense that the probability of hopping left is $q$ times the probability of hopping right. Additionally, particles may enter from the left with probability $\alpha$ and exit from the right with probability $\beta.$ It has been observed that the (unique) stationary distribution of the PASEP has remarkable connections to combinatorics -- see for example the papers of Derrida, and Duchi and Schaeffer. We prove that in fact the (normalized) probability of being in a particular state of the PASEP can be viewed as a certain weight generating function for permutation tableaux of a fixed shape. (This result implies the previous combinatorial results.) This proof relies on the matrix ansatz of Derrida et al, and hence does not give an intuitive explanation of why one should expect the steady state distribution of the PASEP to involve such nice combinatorics. Therefore we also define a Markov chain -- which we call the PT chain -- on the set of permutation tableaux which projects to the PASEP in a very strong sense. This gives a new proof of the previous result which bypasses the matrix ansatz altogether. Furthermore, via the bijection from permutation tableaux to permutations, the PT chain can also be viewed as a Markov chain on the symmetric group. Another nice feature of the PT chain is that it possesses a certain symmetry which extends the "particle-hole symmetry" of the PASEP. More specifically, this is a graph-automorphism on the state diagram of the PT chain which is an involution; this has a simple description in terms of permutations.

This is joint work with Lauren Williams (Harvard)

We introduce a new combinatorial construction, called a dual equivalence graph, based on Haiman's 1992 discovery of an equivalence relation on tableaux which is "dual" to jeu-de-taquin. We define a generating function on the vertices of such graphs and show that it is always Schur positive. We outline the construction of a graph on standard k-tuples of young tableaux which we prove is a dual equivalence graph for k <= 3. This gives a combinatorial description of the Schur coefficients of the ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. Recalling Haglund's monomial expansion for Macdonald polynomials, we conclude with a combinatorial formula for the Schur expansion of Macdonald polynomials indexed by a partition with at most 3 columns.

Let $W$ be a finite Coxeter group of rank $n$ and $c$ a coxeter element. The $c$-clusters of $W$ are certain $n$ element collections of roots of $W$, whose definition is motivated by the theory of cluster algebras. The $c$-noncrossing partitions are certain elements of $W$ which form a rank symmetric lattice. The $c$-Cambrian lattice is a certain lattice quotient of the weak order on $W$, defined by Nathan Reading. Nathan Reading has constructed bijections between the $c$-clusters, the $c$-noncrossing partitions and the elements of the $c$-Cambrian lattice. In this talk, based on joint work with Nathan Reading, I will describe a polyhedral picture that makes all of these bijections transparent to describe. Specifically, elements of the $c$- cambrian lattice can be thought of as maximal cones in a certain coarsening of the $W$-hyperplane arrangement. We show that these cones are simplicial and that the simplicial complex they form is combinatorially, though not metrically, equivalent to the cluster complex. The invariant subspaces of noncrossing partitions are the bottom faces of cones in the Cambrian lattice. This picture allows us to assign geometric meanings to several other combinatorial objects from the theory of cluster algebras, such as $g$-vectors and quasi- Cartan companion matrices. At the end, I will sketch some hopes about how the theory might extend to infinite Coxeter groups.