Richard P. Stanley Seminar in Combinatorics

Everybody is invited to make a short 5/10 min talk about an open problem, conjecture, interesting result, or some stuff you are working on. If you would like to talk, please send an e-mail to Alex Postnikov (apost at math.mit.edu) in advance.

The Non-Messing-Up Theorem is a well known sorting result for rectangular arrays of real numbers. The result states that after first sorting the elements within each row of an array and then sorting within each column of the array, the rows remain sorted.

In this talk, we generalize this results to posets, completely defining the set of posets for which there exist two sets of disjoint saturated chains such that for any original labeling, after sorting the labels along both sets of chains, the labels of the chains in the first set remain sorted. This characterization relies on determining certain necessary conditions for posets to have the non-messing-up property, and in each case we exhibit the chain sets for which the property holds.

Finally we discuss non-messing-up posets with reduced redundancy for two notions of redundancy, and the distribution of linear extensions of non-messing-up posets obtained by sorting along the chain sets.

As a consequence of the classification of the finite simple groups, it has been possible in recent years to characterize Steiner t-designs, that is t-(v,k,1) designs, mainly for the parameter t=2 with sufficiently strong transitivity properties. Probably the most general results have been the classification of all point 2-transitive Steiner 2-designs in 1985 by W. M. Kantor, and the almost complete determination of all flag-transitive Steiner 2-designs announced in 1990 by F. Buekenhout, A. Delandtsheer, J. Doyen, P. B. Kleidman, M. W. Liebeck and J. Saxl.

Nevertheless, for Steiner t-designs with parameters t=3,4 such characterizations have remained challenging open problems. In particular, the classifications of all flag-transitive Steiner t-designs with t=3,4 are known as long-standing and important problems.

In this talk, we shall give the complete classifications of all flag-transitive Steiner t-designs with t=3,4. Our approach makes use of the classification of the finite 2-transitive permutation groups. The occurring examples and the most interesting parts of the proofs shall be illustrated.

There is a natural generalization of domino tilings to tilings of a polygon by hexagons, or, dually, configurations of oriented curves that meet in triples. We show exactly when two such tilings can be connected by a series of moves analogous to the domino flip move. These triple-crossing diagrams have connections to Legendrian knots, planar algebras, and the octahedron recurrence.

In his famous book "Combinatory Analysis" MacMahon introduced partition analysis as a computational method for solving problems of counting solutions to linear Diophantine equations and inequalities, counting lattice points in a convex polytope, and computing Ehrhart quasi-polynomials. Recent results by (1998) G.E. Andrews and his co-authors, together with their Omega package, which can be used as a tool for solving such problems, will be introduced. I will present a new approach, which combines the theory of iterated Laurent series and a new algorithm for partial fraction decompositions, and leads to an algorithm, whose running time is much less than that of the Omega package.

This talk is going to be mostly based on my paper, "A Fast Algorithm for MacMahon's Partition Analysis" (accepted by Electron. J. Combin., arXiv: math.CO/0408377).

We give a combinatorial proof of the Rogers-Ramanujan identities by using two symmetries of a new generalization of Dyson's rank. These symmetries are established by direct bijections. We will also show how to extend this proof to Andrews' generalization of the Rogers-Ramanujan identities. This is joint work with Igor Pak.

Young tableaux, beloved of combinatorialists, tolerated by representation theorists and geometers, seem at first glance to be an unruly combinatorial set. I'll define a simplicial complex in which they index the facets, and slightly more general objects (Buch's "set-valued tableaux") label the other interior faces.

The theorem that says we're on a right track: This simplicial complex is homeomorphic to a ball. I'll explain why this is surprising, useful, and shows why Buch didn't discover the exterior faces too.

Finally, I'll explain how algebraic geometry forced these definitions on us (or, "How I made my peace with Young tableaux"). This work is joint with Ezra Miller and Alex Yong.

A chess tableau is a standard Young tableau (SYT) in which orthogonally adjacent entries have opposite parity. Remarkably, the number of 3xn chess tableaux is the same as several other quantities: the number of 3x(n-1) nonconsecutive tableaux (SYT in which i and i+1 never appear in the same row), the Charney-Davis statistic of a 3xn shape, and the number of Baxter permutations of n. Yet there is no obvious bijection between any two of these. Our main result is a pleasant but mysterious bijection between chess tableaux and nonconsecutive tableaux with three rows. Bijections with the Charney-Davis statistic remain an open problem.

Our original motivation was, appropriately enough, composing chess problems. In the last part of the talk we present and explain two chess problems (one by Noam Elkies) that are related to chess tableaux. The problems have the same flavor as the chess problems in Stanley's book EC2.

The definition of a Young tableau and (for the last part of the talk) knowledge of how chess pieces move are sufficient background for the talk; other terminology will be explained.

This is joint work with Ken Fan and Henrik Eriksson.

Freeness of a hyperplane arrangement is defined algebraically using module of derivations. And it has an interesting combinatorial property: Terao's factorization theorem for characteristic polynomial. I will talk about the freeness of extended Catalan/Shi arrangements and its combinatorial corollaries. In the proof, I will discuss a characterization for freeness.

And a possible relation between algebraic properties of the derivation module and combinatorics of characteristic polynomial, such as "positions of zeros", will also be discussed.

In joint work with Tymoczko, we define a set of exponents for each upper order ideal in the poset of positive roots. This generalizes the usual notion of exponents (which we recover when the ideal is the empty set).

The talk deals with two conjectures for these exponents which generalize classic theorems: one concerns a factorization of an analogue of the Poincare polynomial of the Weyl group; the other concerns a factorization of the characteristic polynomial of an associated hyperplane arrangement. We explain a proof of these conjectures in types A, B, and C.

(joint talk with Lie Groups Seminar)

Let M be a complete matching (graph with n disjoint edges) of the set {1,2,...,2n}. A crosssing (respectively, nesting) of M is two edges (i,j) and (k,m) of M such that i<k<j<m (respectively, i<k<m<j). It is well-known that the number of complete matchings of the set {1,2,...,2n} with no crossings or with no nestings is the Catalan number C_n. We discuss how the theory of oscillating tableaux, which originally arose in the representation theory of the symplectic and orthogonal groups and the Brauer algebra, can be used to obtain further results on crossings and nestings of matchings. In particular, if f_n(i,j) is the number of complete matchings of {1,2,...,2n} with at most i mutually crossing edges and with at most j mutually nested edges, then f_n(i,j)=f_n(j,i). Moreover, the Gessel-Zeilberger reflection principle allows the determination of the generating function F_i(x) = ∑_n≥0 f_n(i,∞) x²ⁿ/(2n)!. Similar results hold when matchings are replaced with set partitions, using a variation of oscillating tableaux called vacillating tableaux. This is joint work with William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, and Catherine H. Yan.

This is an account of a joint work with M.Barot and C.Geiss (UNAM, Mexico). Although motivated by the theory of cluster algebras, the talk will be purely combinatorial, so no knowledge of algebraic properties of cluster algebras (including their definition) will be assumed or needed. One should just bear in mind an analogy between cluster algebras and Kac-Moody algebras: both theories share the same classification of finite type objects by familiar Cartan-Killing types. However the underlying combinatorics beyond the two classifications is different: roughly speaking, Kac-Moody algebras are associated with (symmetrizable) Cartan matrices, while cluster algebras correspond to skew-symmetrizable matrices. We discuss an interplay between the two classes of matrices. In particular, we establish a new criterion for deciding whether a given skew-symmetrizable matrix gives rise to a cluster algebra of finite type.

I will describe the quantum multiplication in cohomology of the Hilbert scheme of points in the plane. The operator of quantum multiplication by the divisor class is a curious nonstationary deformation of the quantum Calogero-Sutherland many-body system. Several results and conjectures on the corresponding deformation of Jack polynomials will be presented. Based on a joint work with Rahul Pandharipande.

The associahedron (or Stasheff polytope) is an object appearing in numerous areas of mathematics, from homotopy theory (operads), configuration spaces (particle collisions), statistics (phylogenetic trees), geometric group theory (Coxeter complexes), and combinatorics. Given any graph G, we construct a convex polytope based on G (dubbed the graph-associahedra) with some elegant properties. For example, when G is a path, we obtain the associahedron; when G is a cycle, we obtain the cyclohedron. These polytopes appear naturally with respect to simplicial Coxeter groups, and provide the tiling for certain compactified real moduli spaces.

If M is a finite complemented modular lattice with n atoms and D is a bounded distributive lattice, then the Priestley power M[D] is shown to be isomorphic to the poset of so-called normal elements of D^n, thus solving a problem of E. T. Schmidt from 1974. It is shown that there exist a finite modular lattice A not having M_4 as a sublattice and a finite modular lattice B such that A⊗B is not semimodular, thus refuting a conjecture of Quackenbush from 1985. It is shown that the tensor product of M_3 with a finite modular lattice B is supersolvable if and only if B is distributive, thus proving a conjecture of Quackenbush from 1985.

I'll discuss two families of Laurent polynomials with hyperoctahedral symmetry, both indexed by partitions. The first, Koornwinder's orthogonal polynomials, includes all of the classical (and quantum classical) spherical functions and characters as special and limiting cases, as well as the Jack and Macdonald polyomials. The second, Okounkov's interpolation polynomials, is defined (and overdetermined) by specifying a large collection of zeros. Despite the significant differences in definitions, these two families are in fact closely related. I'll discuss this connection, and show how it leads to new proofs of the known properties of Koornwinder polynomials, as well as proofs of properties not previously discovered.

(joint talk with Lie Groups Seminar)

Ribbon Schur functions are skew Schur functions corresponding to "ribbon" or "border strip" Ferrers shapes, namely, connected diagrams with no 2 x 2 squares. Those with n boxes naturally correspond to integer compositions of n. We give necessary and sufficient conditions for two such compositions to give identical Schur functions. This involves a notion of combining compositions that corresponds to computing descent sets in tensor products of permutations.

In a talk given in this seminar last spring we defined the correlation of holes on the triangular lattice by including them in large hexagons that were grown to infinity so that the holes remained near the center. We showed that if the holes are distributed symetrically about a straight line, then for large distances between the holes the correlation behaves like the electrostatic energy of a two dimensional system of charges corresponding to the holes. Since the dimer statistics is significantly distorted almost everywhere inside hexagonal regions, it arises as a desirable goal to define the correlation of holes in an alternate way, via regions that don't distort dimer statistics, and analyze its asymptotic behavior. In the present talk we define such a correlation and prove that it also reduces to electrostatics in the scaling limit. Our proof applies to general, not necessarily symmetric distributions of the holes.

We discuss a recent result of the speaker, M. Haiman and N. Loehr, which gives a combinatorial formula for the coefficient of a monomial in the Macdonald polynomial. The formula was first discovered by the speaker using experimental methods. Corollaries include a new proof of the +Lascoux-Schutzenberger cocharge formula for Hall-Littlewood polynomials, a combinatorial formula of Sahi and Knop for Jack symmetric functions, and a decomposition of Macdonald polynomials into the LLT polynomials of Lascoux, Leclerc and Thibon.

We present a new combinatorial proof of Vandermonde's determinant and a combinatorial proof for the number of Self-Avoiding-Walks on the lattice Z_2 x Z, approximately 8F_n, where F_n is the nth Fibonacci number.