Richard P. Stanley Seminar in Combinatorics

The semirandom method (Rödl Nibble) is the general approach to prove the existence of something by generating it through many iterations, applying probabilistic reasoning at each step.

One area of Combinatorics where semirandom method has had the greatest impact is graph coloring. In fact, many of the strongest result in graph coloring over the past decade are examples of this method. In this talk we will illustrate how semirandom method works by proving the following result:

Let $G=(V,E)$ be a graph with the sets of lists $S(v)$, one for each vertex $v$ of $G$, such that

• for every vertex $|S(v)|=(1+o(1))d$ and
• for each color $c \in S(v)$, the number of neighbors of $v$ that have $c$ in their list is at most $d$.

Then there exist a proper coloring of $G$ from these lists. This result is asymptotically tight.

(joint work with Bruce Reed)

Let W be a Coxeter group generated by a set S, and suppose we're given a word Q (an ordered list of elements of S) as well as an element w in W. The subword complex _$\delta$(Q,w) is a simplicial complex whose faces are subwords of Q, with facets defined by the following:

a subword P of Q is a reduced expression for w   iff   Q\P is a facet of _$\delta$>(Q,w).

Taking W = S_n and Q = a certain reduced expression for the long element yields the main examples, whose facets correspond to the rc-graphs of Fomin-Kirillov and Bergeron-Billey; rc-graphs reflect the combinatorics and geometry of Schubert varieties in flag manifolds.

Subword complexes are vertex decomposable (hence shellable) topological manifolds, homoemorphic to balls or spheres. The Hilbert series of their Stanley-Reisner rings can be computed in terms of Demazure products of elements in Coxeter groups (to be defined). The main examples, together with a Gröbner basis theorem for certain determinantal ideals, provide (i) a new proof that Schubert varieties are Cohen-Macaulay in type A; (ii) a combinatorial interpretation for the coefficients of Grothendieck polynomials; and (iii) an algorithm by induction on the weak Bruhat order for producing the monomials in Schubert polynomials. Both (iii) and the sum of lowest degree terms in (ii) recover the Billey-Jockush- Stanley-Fomin formula for Schubert polynomials, while (iii) is a geometrically motivated alternative to Kohnert's conjecture. This talk represents joint work with Allen Knutson.

Paul Erdös attempted, very often successfully, to prove the existence of mathematical objects with particular properties. His methodologies have been adapted with much success to give efficient algorithms for creating those objects. The algorithmic approach, provides new insight into the mathematical proofs. In many cases, as we shall illustrate, it has led to new theorems and conjectures.

We present the Kashaev-Murakami-Murakami conjecture which relates the asymptotic growth rate of certain values of the colored Jones polynomial of a knot to the hyperbolic volume of its complement. We prove the conjecture in the simplest case, the figure eight knot complement, and give heuristic reasons why the conjecture should be true in general; we also explain why you should not trust the heuristics. We close with speculations about relations between hyperbolic geometry and q-hypergeometric functions in general.

In a series of seminal papers, Wilf and Zeilberger (herewith WZ) have established an impeccable bases in the field of Algorithmic Proof Theory. In particular the traditional savoir-faire of proving single and multi-variable special functions, even holonomic, identities is now made automatic.

The present talk aims at exploiting further application of the theory, in a different direction. To wit: a conceptual framework of the WZ methodology will be tied together with discrete-continuous difference- differential forms

as well as winged to systematized Apéry-style irrationality proofs (once regarded as a tour-de-force in Number Theory); hypergeometric and q-hypergeometric series accelerations and constructions of an infinite string of WZ-forms will be given.

The notion of a WZ Cohomology and its computation will be shown as seated at the heart of the matter.

(joint work with D. Zeilberger)

We shall consider several topological spaces equipped with stratifications indexed by integer partitions. In each case we consider the problem of studying homology groups of strata. We shall first describe how to construct various models for computing these groups and then present the following applications:

1. Determining the homology of resonance-free orbit arrangements (with the help of general lexicographic shellability), thereby settling a conjecture of Bjorner for this special case;
2. A combinatorial reproof of Arnol'd theorem regarding the rational homology of the space of monic complex polynomials with at least q roots of multiplicity k;
3. A counterexample to a conjecture by Sundaram and Welker;
4. A computation of the homology groups of the space of hyperbolic polynomials with at least q roots of multiplicity k.

Around 1990 Kashiwara introduced crystal bases which are bases for representations of quantum algebras $U_q(g)$ as $q\to 0$ with very beautiful combinatorial properties. We will review the basic notion of crystals and discuss several embeddings of finite-dimensional affine crystals into crystals of type $A^{(1)}_n$. These embeddings are used to prove fermionic formulas for the one-dimensional configuration sums of the corresponding crystals.

This talk is based on work in collaboration with Masato Okado and Mark Shimozono.

In 1963 Fisher and Stephenson conjectured that the monomer-monomer correlation on the square lattice is rotationally invariant. In this paper we prove a closely related statement on the hexagonal lattice. Namely, we consider correlations of two quadromers (four-vertex subgraphs consisting of a monomer and its three neighbors) and show that they are rotationally invariant.

The purpose of this talk is to introduce a new class of (skew) integer partitions and study their enumerative and combinatorial properties. This class is closely related to Dyck paths, and plays a fundamental role in the computation of certain Kazhdan-Lusztig polynomials of the symmetric group related to Young's lattice.

More precisely, after giving the definitions and some examples, I will state the fundamental combinatorial properties of Dyck partitions, including a combinatorial characterization. I will then illustrate a bijection that allows the enumeration of Dyck partitions. This bijection is based on a statistic on integer partitions that seems to be new. Finally, I will briefly explain the connection between Dyck partitions and the Kazhdan-Lusztig polynomials, and, using this connection, I will derive some new identities for these polynomials. I will conclude by discussing some possible lines of further investigation, and in particular possible analogues of Dyck partitions for other Coxeter groups.

A few years ago, Robin Forman established the notion of a discrete Morse function. We will describe a way of constructing a discrete Morse function with a relatively small number of critical cells from any lexicographic order on the saturated chains of a graded poset. This gives a tool for computing poset Möbius functions via the Morse inequalities and for proving that certain poset order complexes are collapsible or homotopy equivalent to a wedge of spheres. In particular, we apply this to the poset of partitions of a multiset. This is joint work with Eric Babson.

Given an $n \times m$ unimodular matrix $A$ and an integral right hand side $b$. We consider the counting function $\phi_A(b)= | {x : Ax=b, x \geq 0 } |$. The functions $\phi_A(b)$ appear in many different areas including Representation Theory (Kostant partition functions) and Statistics (Contingency tables). It is known that $\phi_A(b)$ is a piecewise polynomial function in terms of the parameters $b$ and the degree of the polynomials components is $m-n$. The domains of valid polynomiality form the well-known chamber complex appearing in the theory of secondary polytopes. Recently, $\phi_A(b)$ has also been representated as a generating function based on the work on Barvinok and Brion. In this talk we will discuss 1) The different algebraic representations of the counting function $\phi_A(b)$ and how they help to effectively compute concrete answers and derive explicit combinatorial formulas. 2) The geometric structure of the chamber complex and its chambers. This is joint work with Bernd Sturmfels (UC Berkeley).

To a finite set of polyomino prototiles, Conway and Lagarias associate a finitely presented group, and they show that the tiling of a region by the protoset implies the vanishing of a certain group element. They also show that the tiling restrictions thus obtained are always as strong as, and may be stronger than any restrictions obtained by generalized checkerboard colorings.

The Conway-Lagarias technique has only been applied successfully in a handful of cases. We present a strategy for applying the technique which is successful in many cases. We also give a number of new examples where we obtain tiling restrictions that cannot be obtained by generalized checkerboard colorings.

We also discuss tiling restrictions that cannot be detected by the tile homotopy group.

In this talk I investigate the connections not yet understood between the existing combinatorial structures for the construction of Schubert polynomials. These structures are: certain strand diagrams called rc-graphs, increasing labeled chains in the Bruhat order on the symmetric group, balanced labelings of the diagram of a permutation, Kohnert diagrams (which are certain diagrams obtained from the diagram of a permutation by specified moves), and semistandard Young tableaux. Recent research on Schubert polynomials has shown the importance of rc-graphs. Thus, we relate the other structures to rc-graphs by constructing new bijections and by studying the properties of existing bijections. For instance, the construction of Schubert polynomials in terms of increasing labeled chains in the Bruhat order, due to N. Bergeron and F. Sottile, and the construction in terms of Kohnert diagrams, due to A. Kohnert and R. Winkel, were done independently of rc-graphs. In this case, our goal is to construct bijections from rc-graphs to the mentioned structures, and, hence, to give more transparent proofs to the corresponding formulas. On the other hand, S. Billey, W. Jockusch, and R. Stanley, in their work which initiated the study of rc-graphs, constructed a map from rc-graphs to a multiset of semistandard Young tableaux. It is known that the latter are endowed with a crystal graph structure, given by the action of certain operators on tableaux, which are relevant to the representation theory of GL_n(C). We discuss the way in which these operators can be lifted to rc-graphs, as well as some consequences.

We define semiconductor networks, which serve as a model for computer microchips, and discuss the inverse boundary problem for these networks. Simply speaking, we answer the question: "To which extent and how can we identify a computer microchip by boundary measurements?" Interestingly, the theory of semiconductor networks generalizes (and simplifies) the recent results of Berenstein, Fomin, and Zelevinsky on totally positive matrices and double Bruhat cells.

Let us say that a matroid on an ordered set is totally positive if it can be represented by a real k x n matrix with nonnegative maximal minors. The combinatorial classes of semiconductor networks are in one-to-one correspondence with totally positive matroids. A byproduct of our theory is the complete combinatorial description of totally positive matroids.

The following problem was raised by M. Watanabe. Let $P$ be a self-intersecting closed polygon with $n$ vertices in general position. How manys steps does it take to disentangle $P$, i.e., to turn it into a simple polygon, if in each step we can arbitrarily relocate one of its vertices. Gabor Tardos and I can partially answer this question. Our arguments are based on results about crossing numbers of graphs.

On Wednesday April 18, the combinatorics seminar will hold an open problems session. Come find out what other people in the department are thinking about -- or aren't, but think is interesting.

You are invited to submit a problem to present to the seminar. Problems should be presentable in no more than 5 minutes, in a way which makes them accessible to the wide variety of people the combinatorics seminar draws together.

If you know you wish to present a problem, please send me email in advance so I can make sure there's enough time for everyone. Limit yourselves (at least initially) to only one question per person.

Reply to Michael Kleber, kleber@math.mit.edu

Schubert varieties in the flag manifold $SL(n)/B$ play a key role in our understanding of projective varieties. One important problem is to determine the locus of singular points in a variety. In 1990, Lakshmibai and Sandhya showed that the Schubert variety $X_w$ is nonsingular if an only if $w$ avoids the patterns $4231$ and $3412$. In this paper we give an explicit combinatorial description of the irreducible components of the singular locus of the Schubert variety $X_w$ for any element $w\in S_n$. These irreducible components are indexed by permutations which differ from $w$ by a cycle depending naturally on a $4231$ or $3412$ pattern in $w$. Our description of the irreducible components is computationally efficient ($O(n^4)$) compared to the best known algorithms, which were all exponential in time. Furthermore, we give formulas for calculating Kazhdan-Lusztig polynomials at the maximum singular points.

This is joint work with Greg Warrington.

A-hypergeometric systems are linear systems of PDEs that can be thought of as non-commutative analogs of toric varieties. We study the number of linearly independent solutions to these systems, as a function of the parameters, and we reduce a central conjecture in this area to a problem in combinatorial commutative algebra, namely, to describe Cohen-Macaulay toric ideals in terms of the embedded primes of their initial ideals.

Linear programming, the problem of maximizing a linear function over a convex polytope, has been one of the most interesting points of contact between Combinatorics and Computer Science. The most popular algorithm for solving linear programs is the simplex algorithm, which works by walking from vertex to vertex along the skeleton of the polytope.

While the simplex algorithm is known to work very well in practice, its theoretical analyses have been negative or inconclusive. Attempts to prove the Hirsch conjecture on the diameter of polytopes have been a fascinating approach to understanding the simplex algorithm, but even the best results of Kalai and Kleitman do not come close to practical experience. Even if better bounds on the diameters of polytopes exist, worst-case analyses of the simplex algorithm point out that there are inputs on which variants of the algorithm take exponential time. As these analyses do not match practical experience, average-case analyses were performed. In the 1980's, the simplex algorithm was shown to converge in expected polynomial time on various distributions of random inputs, most notably by Borgwardt and Smale. However, the last 20 years of research in probability, combinatorics, and numerical analysis have taught us that these random instances have very special properties that one should not expect to find in practice.

To help resolve the discrepancy between theoretical analysis and practical experience, we propose a new approach to analyzing algorithms that we call smoothed analysis. In smoothed analysis, we measure the performance of an algorithm under slight random perturbations of arbitrary inputs. In particular, we consider Gaussian perturbations of inputs to algorithms that take real and complex inputs, and we measure the running time of algorithms in terms of the input size and the variance of the perturbations.

We show that the simplex algorithm has polynomial smoothed complexity. That is, under a slight random perturbation of the facets of a polytope, there is probably a path of polynomial length from a starting vertex to the vertex optimizing the objective function.

In particular, for every matrix A with entries of absolute value at most 1, every vector c, and every vector b whose entries are 1 or -1, we show that the simplex algorithm using the shadow-vertex pivot rule takes expected time polynomial in 1/ \sigma and the sizes of A and c to solve

If A is well-scaled, then the solution to this program is an approximation to the original.

(This talk is joint with the Applied Math Colloquium)

Descartes' Rule (discovered before 1641) states that a univariate polynomial with exactly m monomial terms has at most m-1 positive roots, and the signs of the coefficients more closely determine the number of positive roots. Strangely, more than three and a half centuries later, there is no analogous sharp bound for systems of multivariate polynomials.

A recent example of Bertrand Haas shows that a pair of real bivariate polynomial equations (where each equation has at most 3 monomial terms) can have as many as 5 roots in the positive quadrant. However, until recently, the best upper bound on the number of roots independent of the degrees (following from more general results of Khovanski) is 248,832. We give an elementary proof that 5 is the correct maximum. Our proof also generalizes to real exponents, systems where one of the equations has more than 3 terms, and counting connected components.

We will discuss a universal procedure for the construction and study of several generating functions arising in combinatorics, within the framework of Hopf algebras.

For several types of combinatorial objects, a natural Hopf algebra will be defined, and a "zeta" functional on it. To these, one associates a "Mobius" functional, a "zeta" polynomial and a "flag" quasisymmetric function, by means of a universal property. The terminology is taken from the case of posets. The basic facts and relationships between these objects hold in general.

Instances of the zeta polynomial are:

1. The zeta polynomial of posets
2. The order polynomial of posets
3. The enriched polynomial of posets
4. The chromatic polynomial of graphs
5. The Tutte polynomial of graphs
6. The Martin polynomial of eulerian graphs.

We will prove a general reciprocity theorem for zeta polynomials, based on simple Hopf algebra theory.

Instances of the flag quasisymmetric function are:

1. The ab-index of graded posets
2. The enumerator of posets partitions
3. The enumerator of enriched poset partitions
4. The chromatic symmetric function of a graph
5. The q-chromatic symmetric function of Stanley
6. A flag version of the Martin polynomial.

Given a set of points in $n$-dimensional Euclidean space, we define a point $x$ to be a $\gamma$-outlier if there exists some direction $w$ in which it is more than $\gamma$ standard deviations from the mean along $w$. Outlier removal is the problem of removing an $\epsilon$ fraction of points so that the remaining subset has no $\gamma$-outliers. We characterize the optimal trade-off between $\epsilon$ and $\gamma$ using a simple algorithm for outlier removal. The algorithm suggests a natural linear ordering of the point set with interesting properties.

It is our hope that this work will be of interest to experimental scientists as well as the mathematics community. For a demonstration, please visit http://theory.lcs.mit.edu/~jdunagan

This is joint work with Santosh Vempala.

In the summer 1982 R. Stanley initiated the study of reduced factorizations of elements of $S_n$. Central to this work was the introduction of a family of symmetric functions indexed by permutations. He conjectured these functions to be Schur positive and proved a number of their interesting properties including the enumeration of certain classes of reduced factorizations. At the same time, in a completely independent development, Lascoux and Schützenberger developed the theory of Schubert polynomials. One of the byproducts of this theory was the first proof (nov 1982) of the Schur positivity of the Stanley symmetric functions. This proof as well as several that appeared in the sequel requires the introduction of a substantial amount of extraneous machinery. In this lecture we show how some the Lascoux-Schützenberger results on Schubert polynomials lead to a completely elementary purely combinatorial proof which uses only reduced decompositions. The crucial ingredient in this proof is a remarkable bijection discovered by David Little. An applet yielding this bijection will be the highlight of the talk.

A composition of birational maps given by Laurent polynomials need not be given by Laurent polynomials; however, sometimes---quite unexpectedly---it does. In a joint work with Sergey Fomin (E-print math.CO/0104241) a unified treatment of this phenomenon is suggested, covering a large class of applications. In particular, we settle in the affirmative a conjecture of D.Gale and R.Robinson on integrality of generalized Somos sequences, and prove the Laurent property for several multidimensional recurrences, confirming conjectures by J.Propp, N.Elkies, and M.Kleber.

Given any real reductive Lie group, there is a simple geometric framework to produce a constructive bijection from (something like) involutions in the symmetric group to (something like) standard Young tableaux. For instance, when the Lie group is GL(n,C), the parenthetical caveats can be removed, and one recovers the classical Robinson-Schensted algorithm. Of course this algorithm is of combinatorial interest, but it also turns up in many representation theoretic guises (such as the computation of Kazhdan-Lusztig cells for the symmetric group). The purpose of this talk is to consider the algorithms that arise for other classical real Lie groups, establish their basic combinatorial properties, and give some representation theoretic applications (such as the computation of Lusztig-Vogan cells).