Richard P. Stanley Seminar in Combinatorics

When we consider the universal family of arrangements which are combinatorially fixed, we have a fiber space over a moduli space of combinatorially equivalent arrangements. Each fiber is the complement of an arrangement. The way in which these moduli spaces are glued together corresponds to combinatorially properties of arrangements. We pose some basic problems and conjectures and answer to some of them.

The "plank problem", open since 1950, is the following conjecture. Suppose that the convex set K is contained in the unit cube of R^n, and meets all of the cube's facets. Suppose further that a collection of planks is given (where "plank" means a strip determined by two parallel hyperplanes orthogonal to one of the axes), and the union of these planks covers K. Then the sum of the planks' widths must be at least 1. We propose an analogy between this problem and familiar concepts from the theory of hypergraphs. This leads to a proof of the conjecture in certain special cases, and to a formulation of a fractional counterpart of the conjecture, which we are able to verify to within a factor of 2. This is joint work with Ron Aharoni, Michael Krivelevich and Roy Meshulam.

The solution of the alternating sign matrix by Zeilberger is likely to be only the end of the first chapter of a very long and interesting story. Here are excerpts from three later chapters, with an emphasis on accessible open problems.

One chapter concerns enumeration of ASMs that are invariant under various symmetry groups, and more generally, the enumeration of constrained alternating sign patterns. I'll discuss experimental work on halved ASMs (largely inspired by some still-obscure results of the physicist Tsuchiya).

Another chapter concerns the densely-packed loop representation of ASMs, and a discovery made by Harvard undergraduates Carl Bosley and Lukasz Fidkowski and later proved by M.I.T. undergraduate Ben Wieland: there is a sense in which alternating sign matrices of order $n$ are governed by the symmetry group $D(n)$ (the dihedral group of order $2n$).

A third chapter concerns the matrix condensation process (due to Dodgson) that inspired Mills, Robbins, and Rumsey to invent ASMs in the first place. Variant forms of condensation give rise to new analogues of ASMs. There are no obvious counterparts of the Mills-Robbins-Rumsey conjecture for these analogues, but there are still interesting enumerative phenomena that await explanation.

Consider the following random model for a growing droplet in the plane. The model has 3 parameters: an update probability $p$, a threshold $\theta$ and a neighborhood of the origin $N$. This neighborhood is a finite symmetric subset of the 2-dimensional integer lattices, and the neighborhood of an arbitrary $x$ in the lattice is $x+N$. The droplet is a random sequence $ A_0 \subseteq A_1 \subseteq \dotsm $ of subsets of the two dimensional integer lattice generated as follows: a point $x$ joins $A_{i+1}$ with probability $p$ if the intersection of $A_i$ and the neighborhood of $x$ is at least $\theta $.

This process, known as stochastic threshold growth, generalizes Eden's model, Richardson's rule and discrete threshold growth. It is known that droplets generated by Eden's model, Richardson's rule or discrete threshold growth converge to limiting shapes. In this talk, we discuss a combinatorial lemma that is central to the proof that limiting shapes exist for stochastic threshold growth.

Generalized Kostka polynomials are $q$-analogues of tensor product multiplicities. They can be expressed as generating functions of highest weight vectors of $U_q(sl_n)$-crystals. Extending the $U_q(sl_n)$-crystal structure to a $U_q(\widehat{sl}_n')$-crystal structure gives rise to level-restricted generalized Kostka polynomials.

We present new general fermionic formulas for the level-restricted generalized Kostka polynomials. Fermionic expressions originate from the Bethe Ansatz and can be combinatorialized by rewriting the expressions as weighted sums over sets of rigged configurations. We sketch the proof of the fermionic formula for the level-restricted generalized Kostka polynomials. To this end we review a recently established statistic-preserving bijection between Littlewood--Richardson tableaux and rigged configurations, and show that it is well-behaved with respect to level-restriction. By taking appropriate limits, the fermionic formulas for the level-restricted generalized Kostka polynomials also give rise to new fermionic formulas for type $A$ branching functions.

This talk is based on the following two preprints: (1) A.N. Kirillov, A. Schilling and M. Shimozono, A bijection between Littlewood-Richardson tableaux and rigged configurations, math.CO/9901037. (2) A. Schilling and M. Shimozono, Fermionic formulas for level-restricted generalized Kostka polynomials and coset branching functions, in preparation.

Steinberg showed that the Robinson-Schensted (R-S) correspondence describes the relationship between two natural labelings of the irreducible components of an algebraic variety, sometimes called Steinberg's variety of triples. We give a similar interpretation, through some algebric varieties, of a variant of the R-S correspondence, conceived by Stanley and Sundaram and modified by Roby, which links the Brauer diagrams (also regarded as fixed-point-free involutions) with updown tableaux (also called oscillating tableaux). The talk will include a correction to a former preprint by the speaker, as well as some recent developments.

We briefly recall the basics about Mobius inversion on partially ordered sets. Using this, we introduce an inversion principle for real-valued functions on finite modules. As an application, we present a combinatorial proof for MacWilliams' equivalence theorem for linear codes over finite Frobenius rings.

In the early 1970's the British physicist Ron Atkin proposed the use of simplicial complexes to analyze connectivity in social systems, like cities, committee structures, etc. Since then, Atkin's ideas have been developed further, resulting in a new combinatorial homotopy theory of simplicial complexes. In this setting, a graded group is associated to a simplicial complex, similar to the fundamental group of a topological space. However, the resulting theory is very different from classical combinatorial homotopy theory. In this talk, we introduce this theory and show that it provides a novel approach to the combinatorics of geometric lattices.

Dale Peterson has defined and studied what he calls "lambda-minuscule" elements of (symmetrizable Kac-Moody) Weyl groups. These elements can be encoded by, or even identified with, a certain class of labeled partially ordered sets. In type A, the posets are Young diagrams. In total, there are 17 "irreducible" families of these posets, 16 of which have infinitely many members.

As has become increasing clear in ongoing work of Robert Proctor, there is an amazingly rich combinatorial theory hidden in these posets, generalizing much of the classical combinatorics of Young diagrams. For example, there is an explicit product formula, due to Peterson (refined later by Proctor) for the number of reduced expressions for any lambda-minuscule element. This generalizes the famous hooklength formula of Frame-Robinson-Thrall for counting standard Young tableaux.

In this talk, we will survey the subject matter, including various characterizations, classifications, and applications.

Two years ago, just out of curiosity, we (Clara Chan and I) studied some methods for calculating the volume of B_n, the set of n by n doubly stochastic matrices (nonnegative real square matrices with all row and column sums equal to 1). The standard method had been based on the counting of magic squares (non-negative integer square matrices with constant row and column sums). We decided to investigate a different method, based on work of Richard Stanley, which amounted to counting the simplices in a triangulation of B_n into simplices all of the same volume. A byproduct of the method was that we were able to calculate the volume of any face of B_n.

While there does not appear to be any simple formula for the volume of the B_n itself, we discovered that there was a certain face, the set of doubly stochastic matrices (x_{ij}) with x_{ij}=0 for j>i+1, for which the volume was given essentially as a product of the first so many Catalan numbers.

Working with David Yuen, we found a class of combinatorial objects in one-to-one correspondence with the simplices in a decomposition of our face into simplices of the same volume.

We will describe an argument of Doron Zeilberger which establishes the Catalan product for the cardinality of the class of combinatorial objects by using an extension of "Morris's Constant Term Identity".

A problem in the foundations of probability inspired the definition of a "scale" -- a certain kind of increasing function whose domain is a Boolean algebra and whose range is a poset. A scale rho : A ---> S induces operations on S that make S behave in some ways like a Boolean algebra, satisfying a modular law and some de Morgan laws. In some other ways, S behaves quite unlike Boolean algebras -- in particular, in some cases S is not a lattice. Examples of scales will be exhibited, basic properties of scales will be proved, and their application to probability will be explained.

A graph is called {\em $H$-free} if it does not contain $H$ as an induced subgraph. Erdos and Hajnal raised the following question. Is it true that for every graph $H$ there exists $\varepsilon(H)>0$ with the property that any $H$-free graph with $n$ vertices contains either a complete or an empty subgraph with $n^{\varepsilon(H)}$ vertices? We answer this question in the affirmative for some special classes of graphs, including graphs defined by geometric means.

The toric Hilbert scheme parameterizes all ideals in a polynomial ring with the same multigraded Hilbert series as a given toric ideal. Such ideals were first introduced in a special case by Arnold, and in generality by Sturmfels. The ideals and scheme have also been studied by Korkina, Peeva and Gasharov, and Peeva and Stillman. One central open problem on toric Hilbert schemes is whether they are always connected. I will describe joint work with Rekha Thomas (Texas A&M) which connects this question to the Baues problem of geometric combinatorics. We construct a graph on the monomial ideals in scheme which is connected if and only if the scheme is connected.

Mallows and Riordan showed in 1968 that labeled trees with a small number of inversions are related to labeled graphs that are connected and sparse. Wright enumerated sparse connected graphs in 1977, and Kreweras related the inversions of trees to the so-called "parking problem" in 1980. A combination of these three results leads to a surprisingly simple analysis of the behavior of hashing by linear probing, including higher moments of the cost of successful search.

We study the behavior of the random graph with respect to first order statements.

First order statements are built from the atomic formulae $x=y$ and $x\sim y$ ($x$ is connected to $y$) with logical connectives and quantors ranging over the vertices of the graph. A simple first order statement is that every edge is in a triangle. This statement holds almost always for $G(n,n^{-\alpha})$ if $\alpha<1/2$ and holds almost never if $\alpha>1/2$. The limit probability ``jumps'' at $\alpha=1/2$. Here $G(n,p)$ is the random graph with $n$ vertices, whose edges are present independently with probability $p$.

A celebrated result of Shelah and Spencer from '88 is the following 0-1 low: any first order sentence on $G(n,p)$ with $p=n^{-\alpha}$ holds almost always or almost never if $\alpha$ is irrational. We study how this limit probability can depend on $\alpha$. Surprisingly, for some sentences the limit jumps infinitely often. We identify a number theoretic and a computational complexity condition, that together give a complete characterization of the 0-1 functions that arise as limits. An interesting consequence of our result characterizes the unary languages $L$ such that for some first order sentence the limit probability jumps at exactly the values $1/2+1/k$ for $k\in L$. These are exactly the unary languages in the polynomial time hierarchy $PH$.

Most of these results are joint work with Joel Spencer.

Let $K$ be a finite set of vectors in $\mathbb R^n$. Let ${\operatorname{conv}^*}(K)$ be the convex hull of $\{O\}\cup K$. Given any linear order $\prec$ on $K$, say $K= \{ v_1, v_2, v_3, \ldots, v_m\}$ with $ v_1\prec v_2 \prec v_3 \prec \cdots \prec v_m$, we define the notion of a \emph{$\Delta_\prec$-basis} on the linear matroid $\mathcal{M}(K)$ whose underlying set of vectors is $K$ and present a local triangulation of ${\operatorname{conv}^*}(K)$ determined by $\prec$. We will specifically look at the polytopes ${\operatorname{conv}^*}(A_n^+)$, where $A_n^+$ is the set of positive roots of the root system $A_n$, and polytopes similarly associated to other root systems. We will talk about their volumes, shellabilities, and Ehrhart polynomials and, while doing so, introduce the C_n anaolog of Catalan numbers and Narayana numbers.

A quiver variety is a general type of degeneracy locus obtained by putting arbitrary rank conditions on a sequence of vector bundles with maps between them. Fulton and I proved a formula for the cohomology class of a quiver variety, which expresses this class as a linear combination of products of Schur polynomials. We have conjectured that the coefficients in this linear combination are non-negative and given by a generalized Littlewood-Richardson rule. I will describe this conjecture, as well as applications of the formula to Schubert polynomials and Stanley symmetric functions.

The solution of the alternating sign matrix by Zeilberger is likely to be only the end of the first chapter of a very long and interesting story. Here are excerpts from three later chapters, with an emphasis on accessible open problems.

One chapter concerns enumeration of ASMs that are invariant under various symmetry groups, and more generally, the enumeration of constrained alternating sign patterns. I'll discuss experimental work on halved ASMs (largely inspired by some still-obscure results of the physicist Tsuchiya).

Another chapter concerns the densely-packed loop representation of ASMs, and a discovery made by Harvard undergraduates Carl Bosley and Lukasz Fidkowski and later proved by M.I.T. undergraduate Ben Wieland: there is a sense in which alternating sign matrices of order $n$ are governed by the symmetry group $D(2n)$ (the dihedral group of order $2n$).

A third chapter concerns the matrix condensation process (due to Dodgson) that inspired Mills, Robbins, and Rumsey to invent ASMs in the first place. Variant forms of condensation give rise to new analogues of ASMs. There are no obvious counterparts of the Mills-Robbins-Rumsey conjecture for these analogues, but there are still interesting enumerative phenomena that await explanation.

(Talk rescheduled from 9/17, when the speaker's plans were stymied by a hurricane.)

The Kazhdan-Lusztig polynomials $P_{x,w}$ are associated to a pair of elements in any finite reflection group. These polynomials have important interpretations in representation theory. The $P_{x,w}$ have a simple recursive definition that has not been conducive to expression in closed form. Deodhar proposes a non-constructive combinatorial framework for determining the $P_{x,w}$. Using this framework, we explicitly describe the combinatorics of the $P_{x,w}$ in the case where our group is the symmetric group and the permutation $w$ is 321-hexagon-avoiding. Our formula can be expressed in terms of a statistic on all subexpressions of any fixed reduced word for $w$. These results give a simple criterion for the Schubert variety $X_w$ to have a small resolution. We conclude with an explicit method for completely determining the singular locus of $X_w$ when $w$ is 321-hexagon-avoiding. The results extend easily to those Weyl groups whose Coxeter graphs have no branch points ($B_n$, $F_4$, $G_2$).

Let P be a partially ordered set (poset). Consider the poset of all down-sets of P (downward-closed subsets), ordered by set-inclusion. For the purposes of this lecture, this will be what is meant by a "distributive lattice."

A distributive lattice L with a least element is "finitary" if every interval is finite. A function f from the set of natural numbers to itself is a "cover function" for L if every element with n lower covers (immediate predecessors) has f(n) upper covers (immediate successors). Richard P. Stanley introduced this notion when considering posets related to the Fibonacci numbers. In this paper, all finitary distributive lattices with non-decreasing cover functions are characterized. A 1975 conjecture of Stanley's is thereby settled.

If time permits, the finite distributive lattices that are sequentially differential posets will be discussed. There may also be a discussion concerning the differential posets that are lattices.

The Bruhat order of the symmetric group describes adjacency of Schubert cells in the complex flag manifold. This geometric model does not, however, explain the phenomenon discovered by A.Bjorner in the early 1980s: each interval in the Bruhat order (in fact, of any Coxeter group) is the face poset of some regular cell complex.

I will report on recent progress on the problem, posed by Bjorner, of finding natural geometric realization of this complex. This is joint project in progress with Michael Shapiro (KTH Stockholm).

For a finite acyclic digraph G we associate a convex polytope P called the *flow polytope* of G. We will discuss some of the interesting combinatorial properties of P, including unexpected connections with Kostant's partition function for the root system A_n. In particular, we will indicate how the theory of acyclic flow polytopes is an analogue of the theory of P-partitions.

For any $n$, $k$, $n\ge 2k>0$, we construct a set of $n$ points in the plane with $ne^{\Omega\left({\sqrt{\log k}}\right)}$ $k$-sets. This improves the bounds of Erd\H os, Lov\'asz, et al. As a consequence, we also improve the lower bound of Edelsbrunner for the number of halving hyperplanes in higher dimensions.