Richard P. Stanley Seminar in Combinatorics

We develop a theory of counting nonintersecting lattice paths by the major index and generalizations of it. As application we prove refinements of two theorems in plane partition theory, the Bender-Knuth and MacMahon (Ex-)Conjectures, respectively.

Let M be a finite set and P a "property" enjoyed by some subsets X of M. With N(P) we denote the number of X in 2^M with property P. For any properties P_1,...,P_n let C=C(P_1,...,P_n) be the family of those X in 2^M which enjoy {\it all} properties P_i. According to the well known principle of "inclusion-exclusion" one has

|C| = N(P_1 wedge ... wedge P_n) =
sum_{1 <= i <= n} N(P_i)
- sum_{1 <= i < j <= n} N(P_i vee P_j)
+ ...

Unfortunately 2^n-1 many terms N(P_i vee P_j vee ... vee P_k) need to be added and substracted from each other on the righthand side. Moreover, sometimes there is no easy way to compute the terms themselves. We shall present an often better method for determining |C|, which is based on a principle of "exclusion". It is demonstrated for arbitrary _closure_systems_ C (which fit a lot of applications in Algebra and Combinatorics), but we believe that variations would apply to other counting problems as well.

Let G be a finite graph. We will define a symmetric function X_G = X_G(x_1,x_2,...) which generalizes the chromatic polynomial of G. Classical results on chromatic polynomials dealing with Mobius functions and acyclic orientations can be extended to X_G. For certain graphs G, the expansion of X_G in terms of elementary symmetric functions is related to the theory of Hecke algebras and Kazhdan-Lusztig polynomials.

The classical sequence 1,1,1,2,5,16,61,272,1385,... occurs in many combinatorial problems. It has recently been discovered that the same sequence governs the topological classification of Morsifications of simplest degenerate critical points of smooth functions. This observation leads to the generalizations of the Euler and tangent numbers which can be associated with any simple Lie algebra or even to any Coxeter group. This gives new information even in the classical case (corresponding to the sl(n) algebras and to the symmetries of simplices), for instance new congruences for the classical Euler and Bernoulli numbers, generalising those found by Kummer, von Staudt and Knuth.

Kirillov and Reshetikhin introduced rigged configurations as a new way to calculate the entries K_{\lambda\mu}(t) of the Kostka matrix. Macdonald defined the two-parameter Kostka matrix whose entries K_{\lambda\mu}(q,t) generalize K_{\lambda\mu}(t) . I use rigged configurations and a formula of Stembridge to provide a combinatorial interpretation of K_{\lambda\mu}(q,t) in the case where \mu is a partition with no more than two columns. In particular, I show that in this case, K_{\lambda\mu}(q,t) has nonnegative coefficients.

Attempting to find "exact" asymptotic formulas for the number of plane partitions various byproducts are obtained: generalized Dedekind sums, values of Bernoulli polynomials at rational points. Wilf's conjecture is proved.

If P and Q are finite posets with the fixed point property, does the product PxQ also have this property? In 1985, E. Corominas introduced the notion of "projective" (idempotent trivial) poset to attack this problem: the fixed point property is preserved under products if the so-called "minimal automorphic" posets are projective. We prove that the projection property is equivalent to quasiprojectivity (tightness) for posets of arbitrary cardinality; universal algebraic methods can then be used to determine if a poset is projective. We relate Corominas' conjecture to the notion of representability by irreducibles in varieties of ordered sets.

Submodular set-functions arise in a variety of fields, including combinatorics, probability and geometry. Classical examples include the rank function of a matroid, the cuts in a directed or undirected graph, the probability that a subset of events do not simultaneously occur, or the logarithm of the volume of the parallelepiped spanned by a subset of linearly independent vectors.

We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting families, the problem can be reduced to a sequence of submodular function minimizations over all subsets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets, leading to a characterization of the minimum even cut in a graph. These results generalize and unify many classical results in combinatorial optimization.

This is joint work with V.S. Ramakrishnan.

Consider the family of integer programs of the form

Min cx : Ax = b, x in N^n

obtained by varying the right hand side vector b but keeping A and c fixed. We describe a unique minimal test set for this family, called the reduced Grobner basis. Algebraically, this test set arises as the reduced Grobner basis of the toric ideal associated with A. We present a combinatorial version of Buchberger's Grobner basis algorithm for this class of problems.

As a special case we discuss the perfect f-matching problem on the complete graph K_n. An explicit description is given of test sets for all graphs with eight vertices or less. We briefly indicate the role of the above test sets in studying triangulations of the second hypersimplex, that is, the convex hull of columns of the vertex-edge incidence matrix of K_n.

Using links and joints, one can build an "erector set" type linkage in which angles are free to change, but lengths and collinearity properties are fixed. A problem in computer-aided design raised the question of when such a linkage can be embedded in an integer lattice, assuming one is allowed to shift lengths by epsilon, but collinearity properties must be preserved. What is the minimal epsilon that will allow an embedding where each of the edges has its endpoints on integer vertices in the lattice?

We show here that the question of whether a linkage can be embedded on the integer lattice is NP-complete, an unhappy situation. But all is not lost: for applications, it is quite reasonable to assume that lengths are bounded, as are the number of "co-incident" polygons. With these caveats, we show there is a polynomial time solution to the problem.

We note that the problem has some nice ties to number theory: the linkage can be embedded only if each of its links can, and this can happen if and only if each of the links has a length whose square can be written as the sum of two squares. We explore these connections further in the paper.

Define G to be stable if the normalized chromatic difference sequence of G is equal to the normalized chromatic difference sequence of G times G, the Cartesian product of G with itself. Zhou has shown that circulants and Cayley graphs are stable. The chromatic difference sequence of a stable graph G begins with omega terms equal to alpha where omega is the clique number and alpha is the independence number of the graph. If G contains partitionable graph H with the same clique size, then the omega+1st term is at least alpha(G)/alpha(H). For stable graphs of large odd girth, this gives upper bounds on the independence ratio of the graph which agree with previously known lower bounds. We also prove nice bounds on the independence ratios of circulants.

Abstract: Finite cell decompositions of surfaces (or "fat graphs") appear in the perturbative expansion of matrix models. The latter yield tau-functions for discrete or continuous integrable systems. Suitable specializations solve combinatorial problems on the moduli space of algebraic curves of given genus such as virtual characteristic (Harer, Zagier, Penner) or intersection numbers of stable characteristic classes (Witten, Kontsevich). The same data record unramified arithmetic coverings of P_1/{0,1,infinity}. This gives an action of Gal(Qbar / Q) on fat graphs (Belyi, Grothendieck, Voevodsky, Shabat). We shall attempt to give an overview of the (few) results and (many) open problems in this area.

Refreshments will be served from 3:45 p.m. in Room 2-349

Our aim in this talk is to give a simple, nonrecursive, combinatorial formula for any Kazhdan-Lusztig polynomial of any Coxeter group W, and to study some consequences of it. The main idea involved in the proof and statement of this formula is that of extending the concept of the R-polynomial to any (finite) multichain of W (so that, for multichains of length 1, one obtains, apart from sign, the usual R-polynomials). Our main result expresses the Kazhdan-Lusztig polynomial of any Bruhat interval as the sum of the R-polynomials of its multichains.

We then use our main result to obtain combinatorial formulas for each coefficient of any Kazhdan-Lusztig polynomial. We use one of the special cases to characterize in purely combinatorial terms those Bruhat intervals whose Kazhdan-Lusztig polynomial equals the g-polynomial (as defined by R. Stanley) of the dual interval. As a consequence of it we obtain explicit formulas for the Kazhdan-Lusztig polynomials of intervals which are lattices. We also use our main result to obtain upper and lower bounds for the coefficients of Kazhdan-Lusztig polynomials. In particular, we verify a conjecture of Lascoux- Schutzenberger for all sufficiently long intervals. Finally, we briefly sketch how it is possible to obtain analogues of all the results in the talk for inverse Kazhdan-Lusztig polynomials.

Though the Hilbert scheme parametrizing subschemes of projective n-space has been the object of much investigation, its structure remains largely a mystery. This talk will combine elements from combinatorics, Grobner basis theory, and algebraic geometry to bound the component-wise radius of the Hilbert Scheme.

The Young-Fibonacci lattice is an interesting example of a differential poset, of which another fundamental example is Young's lattice of partitions ordered by inclusion of Young diagrams. With Young's lattice are naturally associated the symmetric groups and the ring of symmetric functions. In this talk, I construct a Young-Fibonacci analogue of

1. the group algebra of the symmetric group,
2. the ring of symmetric functions, and
3. the character ring of the symmetric group.

In the vein of recent work of Sagan, Yeh and Ziegler, we study extremal problems connected with the Mobius function of three families of subsets from O_n, the lattice of faces of the n-dimensional octahedron: lower order ideals, intervals of rank-selections, and arbitrary rank-selections. In each case, we illustrate the techniques used to determine the extremal configurations. Also, we briefly describe other results and present/future research.

In this lecture we will combine three very different bodies of recent work, one combinatorial and two algebraic. The first is the study of the posets of partitions where every block size is congruent to 1 mod k+1. The second is the study of certain algebraic structures called Lie k-algebras and Liebnitz k-algebras. The third is the theory of Koszul duality for operads. Although we will not assume any background knowledge in these subject areas we will try to give enough of an idea about them to demonstrate some of their close connections.

Let C be a q-ary covering code with covering radius one. We give lower and upper bounds for the number of elements of C that lie in a fixed subspace of {0,...,q-1}^n. These inequalities lead to lower bounds for the cardinality of C that improve on the sphere covering bound. More precisely we show that, if (q-1)n+1 does not divide q^n and if (q,n) is not in {(2,2),(2,4)}, the sphere covering bound is never reached. This enables us to characterize the cases where the sphere covering bound is attained, when q is a prime power. We also present some improvements of the already known lower bounds for binary and ternary codes.

D. Foata and M.-P. Schutzenberger showed that the number of permutations in S_n with length i and major index j is equal to the number of those with length j and major index i. The two-variable generating function of this distribution is expressed as a sum of

K_{lambda,(1^n)}(q) . K_{lambda,(1^n)}(t)

for all partitions lambda of n.

Generalizing this identity, we give a combinatorial interpretation of the sum of

K_{lambda,mu}(q) . K_{lambda,(1^n)}(t),

for any fixed partition mu of n. This interpretation is different from that in terms of Lascoux-Schutzenberger's charge and the major index.

In showing the generalized identity, we look at the variety of flags in C^n that are stable under a nilpotent matrix N. We note that Staltenstein's partition of this variety into affine spaces is explicitly achieved by taking the N-stable parts of Schubert cells.

Recently, a combinatorial interpretation of stable Schubert polynomials in terms of braid configurations was found, based on a well-known geometric interpretation of the Yang-Baxter equation. In the particular case of 321-avoiding permutations, these polynomials are the skew Schur functions. Each of corresponding braid configurations breaks up into two families of paths which are exactly the Gessel-Viennot paths for the two Jacobi-Trudi determinants. An alternative description of this construction relates skew Schur functions to reduced decompositions in the Temperley-Lieb algebra. Generalizations and applications include super-Schur functions, binomial determinants, and the $P$- and $Q$-Schur functions.

This is a joint work with X. G. Viennot.

McMullen's conjecture characterized the f-vectors of simplicial convex polytopes Delta. Stanley's proof of (one direction of) this conjecture used the cohomology H^*(X, C) of the toric variety X associated to Delta. Let omega in H^2(X, C) be the Lefschetz hyperplane class. Key facts for Stanley's proof were that the quotient H^*(X, C)/(omega) is a graded ring generated by H^2.

When Delta is an arbitrary rational convex polytope, one can ask about the analogues in intersection cohomology: is IH^*(X, C)/(omega) a ring, and is it generated by IH^2 ? I will discuss preliminary results on these questions, as well as approaches for computing the intersection cohomology.