Richard P. Stanley Seminar in Combinatorics

The study of the action of the Steenrod algebra on the mod p cohomology of spaces has many applications to the topological structure of those spaces. In this talk we present some combinatorial formulas for the action of Steenrod operations on the cohomology of Grassmannians, both in the Borel and the Schubert picture. We consider integral lifts of Steenrod operations, which lie in a certain Hopf algebra of differential operators. The latter has been considered recently as a realization of the Landweber-Novikov algebra in complex cobordism theory; it also has connections with the action of the Virasoro algebra on the boson Fock space. Our formulas for Steenrod operations are based on methods which have not been used before in this area, namely Hammond operators and the combinatorics of Schur functions. We also discuss applications of our formulas to the geometry of Grassmannians.

Note: Preprint available.

Our goal is to generalize the following known matching property of lattices as far as possible to an arbitrary abelian group. Let G be a lattice (discrete additive subgroup of R^n). Suppose we are given m lattice points and m direction vectors from G. Then it is possible to pair the lattice points with the direction vectors in one-to-one fashion so that the sum within each pair is not one of the given lattice points; moreover, this can be done in such a way that the pairing is uniquely determined by the lattice points, direction vectors and multiset of sums. After discussing two approaches to proving the lattice formulation (one due jointly to Alon, Fan, Kleitman and Losonczy), we describe how the Dyson e-transform, the Cauchy-Davenport inequality and other tools from additive number theory can be used to prove the existence of admissible pairings (matchings) in a more general setting.

Note: Preprint available.

Consider the problem of tiling a region on a square grid by a given set of tiles. You can use the same tile many times, but only translations are allowed (no rotations or reflections). There are two types of questions you can ask:

• (1) Are there any tilings of a given region?
• (2) If there are, what do these tilings look like?

While most people were traditionally concerned with the first question, in our work we are dealing with the second question. Namely, in a case of ribbon tiles (also called rim hooks in a different context) we were able to find all the affine linear relations for the number of times each tile can occur in a tiling. This generalizes Conway-Lagarias Theorem and explains certain results regarding characters of the symmetric groups. The crucial part of the proof is the Stanton-White bijection and its generalization. We also give some applications to tileability (the first question).

(During the talk, a puzzle and its solution were handed out; these are available over the Web.)

We give a geometric interpretation of S. Sundaram's correspondence, or the one modified by T. Roby, between the Brauer diagrams on 2n points and the updown tableaux of length 2n which both start and end at the empty shape.

Our interpretation is an analogue of R. Steinberg's result on the original Robinson-Schensted correspondence, which describes the relative position of a generic pair of complete flags fixed by a unipotent transformation and having a prescribed pair of sequences of types under it.

Our result uses pairs of a nondegenerate symplectic form and a complete flag instead of pairs of complete flags, and has been inspired by works by Oshima and Matsuki on orbit decompositions of symmetric spaces.

We show that the Kazhdan-Lusztig polynomials (and, more generally, parabolic KL polynomials) for the group S_n coincide with the coefficients of the canonical basis in the nth tensor power of the fundamental representation of the quantum group U_q SL_k. We also use known results about canonical bases for U_q SL_2 to get a new, simple proof of the recurrent formulas for KL polynomials for maximal parabolic subgroups (geometrically, this case corresponds to Grassmanians), due to Lascoux-Schutzenberger and Zelevinsky. This is joint work with I. Frenkel and M. Khovanov.

Gromov-Witten invariants of flag manifolds generalize the intersection numbers of Schubert varieties (aka Littlewood-Richardson coefficients). Their study and explicit calculation is an important problem in quantum Schubert calculus. The aim of the talk is to present certain symmetries of these invariants under the action of cyclic groups. This allows one to calculate 1/n of all these invariants.

For each partition with parts less than n, there is a variety of partial flags of subspaces in an n-dimensional vector space. We use V. Kac's method of quiver representations to answer the question: For which tuples of partitions does the group $GL(n)$ act on the corresponding product of partial flag varieties with finitely many orbits? (For a single flag variety, these orbits are Schubert cells.) We describe the poset (Bruhat order) given by closures of these orbits. Joint work with J. Weyman and A. Zelevinsky.

This is a joint work with Dave Bayer (Columbia Univ) and Bernd Sturmfels (Univ of California, Berkeley).

Let M be a monomial ideal in the polynomial ring S=k[x_1,... ,x_n] over a field k. We are interested in the problem, first posed by Kaplansky in the early 1960's, of finding a minimal free resolution of S/M over S. The difficulty of this problem is reflected in the fact that the homology of arbitrary simplicial complexes can be encoded via the Stanley-Reisner correspondence into the multigraded Betti numbers of S/M. In particular, the minimal free resolution may depend on the characteristic of k.

We introduce an approach of resolving by encoding the whole resolution (including the differential maps) into a single simplicial complex. We prove that generically such a resolution is minimal and comes from the boundary of a polytope. We resolve (non-minimally) an arbitrary monomial ideal by deforming it to a generic one.

Background: I will assume familiarity with Section 11 in Chapter I in the book "Combinatorics and commutative algebra" by R. Stanley.

We apply Groebner basis theory to study the A-hypergeometric system of differential equations which was defined by Gel'fand, Kapranov and Zelevinsky for any lattice configuration A. This system is holonomic; its rank equals vol(A) if the toric ideal of A is Cohen-Macaulay or if the parameters are generic, but its rank may exceed vol(A) otherwise. To bound the rank and to construct series solutions for all parameters values, we introduce the initial ideal of the A-hypergeometric system with respect to a suitable term order. The initial ideal contains the ideal of indicial polynomials (in the sense of Frobenius), and they are equal generically. Our goal is to determine all solutions of the indicial ideal and to identify which ones arise from A-hypergeometric series. In this talk we present results for the case when the underlying triangulation of A is unimodular. This is joint work in progress with Nobuki Takayama (Kobe) and Mutsumi Saito (Sapporo).

Note: Preprint available.

Let G be a classical group, T a maximal torus in G, and B a Borel sub group containing T. Let X be any Schubert variety in G/B, and let v be any T-fixed point in X. We give an explicit description of the tangent space to X at v.

Any and all combinatorialists are invited to prepare a short 5-15 minute presentation on a resent result or open problem. Those who are interested in speaking should send e-mail to Jim Propp (propp@math.mit.edu) ahead of time. Hopefully, everyone who wants to speak will get a chance.

Let a(i,j) be real numbers for i , j > 0, satisfying a recursion Sum a(i-r,j-s) c(r,s) = 0 for all but finitely many (i,j), where phi (x,y) := Sum c(r,s) x^r y^s is a given polynomial. The problem of determining asymptotics for a(i,j) is more complicated than in the one variable case for two reasons. First, in the case where phi(0,0) = 0, the generating function is not rational, and some care is needed in obtaining it. Secondly, obtaining asymptotics from the generating function is not nearly so straightforward as it is in the one variable case. I will discuss both these problems, give examples, some motivation, and partial solutions. This is work in progress.

We start by giving a brief overview of the basics of rook theory and q-rook polynomials. Then we extend a result of Solomon, which shows that q-rook polynomials count the number of matrices over finite fields satisfying certain constraints. This eventually leads to a new statistic for Garsia and Remmel's q-hit polynomial. Both this new statistic "mat" and another statistic for the q-hit polynomial \xi recently introduced by Dworkin are shown to induce different multiset Mahonian permutation statistics for any Ferrers board. In addition, for the triangular boards they are shown to generate different families of Euler-Mahonian statistics. For these boards the \xi family includes Denert's statistic "den", and gives a new proof of Foata and Zeilberger's Theorem that (exc,den) is equi-distributed with (des,maj). The mat family appears to generate a new Euler-Mahonian pair. A proof that the q-hit polynomials are symmetric and unimodal is also discussed.

Note: Preprint available.

In 1928 E. Sperner solved this problem: Given a finite ground set S of size n, what is the largest possible collection of subsets of S such that no two of the subsets are related by containment?

In the last twenty years, a generalization of this problem has been studied, namely: given a finite partially ordered set (poset), what is its largest antichain? (An antichain is a set of elements no two of which are related by the poset's order relation.)

Many interesting posets arise naturally in combinatorics, one of which is partitions of an n-set ordered by refinement. A partition of the n-set [n] = {1,2,...,n} is a collection of pairwise disjoint subsets, called blocks, whose union is [n]. One partition is a refinement of another if the first can be obtained by further partitioning the blocks of the second.

Determining the size of the largest antichain in this partition poset has spawned many general theorems in the subject now known as Sperner Theory. We will trace the study of large antichains in the partition lattice.

Note: Preprint available.

Two polynomials interlace if their roots alternate. The central question in the study of interlacing is

In this talk I will discuss various interlacing preserving linear transformations. For instance, differentiation preserves interlacing, but integration does not.

It is a classical result that if f and g are polynomials with all real roots then f(D)g has all real roots, where D is differentiation. I will show that the bilinear map sending (f,g) to f(D)g preserves interlacing in each argument.

Let F be a finite set of prototiles T_1, T_2,...,T_k. An F-tiling is a global tiling of euclidean space, where every tile is congruent to some T_{\kappa}. If Infl is an inflation-operator, then S(F,Infl) is the "species" of all F-tilings P such that every bounded cluster of P has a congruent copy in some Infl^n (T_{\kappa}). If LMR is a local matching rule, then S(F, LMR) is the species of all F-tilings which satisfy LMR everywhere.

The relationships between the following properties of such species will be discussed:

-- (I) being definable by some inflation,

-- (D) existence of a unique inverse of Infl,

-- (LMR) being definable by some local matching rule,

-- (AP) being aperiodic,

-- (NL) being non-local (not in contradiction to (LMR) !),

-- (R) being repetitive,

-- consisting of 2^{\aleph_0} congruence classes.

(Joint work with R. Thomas and N. R. Natraj)

We study the problem of scheduling n job types on m parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.

Methods of solution currently available -- in integer programming and stochastic programming -- are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Groebner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.

Our algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.

Shub and Smale showed that for certain random polynomial systems, the expected number of real roots equals the square root of the expected number of complex roots. We prove a similar theorem for a new family of polynomial systems and propose a broader conjecture --- the square root volume conjecture (SRVC).

The class of sparse polynomial systems where the SRVC has been proved also includes randomized versions of the following well-known problems from linear algebra: the generalized eigenvalue problem and the matrix polynomial problem.

Our probability measures can all be described via convex geometry, and are natural in a metrically invariant sense, depending on the underlying toric compactification. This talk will be entirely self-contained (no knowledge of toric varieties is assumed).

Note: Preprint available.

Given any affine projection of polytopes P --> Q, Billera and Sturmfels have defined a new polytope, called the fiber polytope of the projection. Its faces correspond to certain induced polytopal subdivisions of Q, called coherent subdivisions. We consider the cyclic polytopes C(n,d), having n vertices on the d-dimensional moment curve, and the canonical projections C(n,d) --> C(n,d') between them. We show that for d'=1, the corresponding fiber polytope has combinatorial structure that is independent of the coordinates used to define C(n,d), namely that of a zonotope with n-2 generators on the (d-1)-dimensional moment curve. We show that the combinatorics of the fiber polytope may vary along with the parameters as soon as d' is at least 2 and classify all triples (n,d,d') for which the property of coherence is independent of the coordinates for any induced subdivision of C(n,d'). This is joint work with Jesu's DeLoera, Victor Reiner and Francisco Santos.

Let A be a finite subset of N^d. An ideal is called A-graded if it has the same Hilbert function as the toric ideal J defined by A. What are the A-graded ideals? The structure of such ideals was first studied by Arnold who related it to continued fractions. Arnold, Korkina, Post, and Roelofs proved that if J defines an affine monomial curve in A^3, then every A-graded ideal is an initial ideal of the toric ideal J. Later Sturmfels studied A-graded ideals in the general case and related their structure to the convexity properties of the set A. In particular, he showed that the monomial A-graded ideals correspond to triangulations of the convex envelope of A. In view of Lee's theorem that A has only regular triangulations if the codimension is 2, Sturmfels conjectured the following generalization of the Arnold-Korkina-Post-Roelofs result: if the toric ideal J has codimension 2, then every A-graded ideal is an initial ideal of J. We prove this conjecture. The proof relies on a combinatorial description of the syzygies of J. This is a joint work with Irena Peeva.

Let C be a category and K be an object in C. One can view a group G acting on K as a functor F from G (viewed as a category) to C. With this viewpoint it is easy to define the quotient K/G as a colimit of F. We shall study the case when K is a category (in particular a poset). Then the quotient always exists and satisfies an important functorial property: it commutes with Quillen's realization functor. Having this functoriality at hand we are able to derive many nice properties of K/G.

Also, with this new definition we get many new and interesting examples of categories deserving the study, one of them being the partition lattice divided by the action of the symmetric group.

We will outline connections to other areas such as representation theory (by disproving the generalized Arnold conjecture due to Sundaram and Welker) and the study of the Mobius function.

Hilbert's 16th problem is partially concerned with the classification of topological types of smooth real projective hypersurfaces. It is clearly important to have available effective methods to produce examples of new topological types. During the 1980's Oleg Viro developed a combinatorial technique for constructing hypersurfaces with given topology. This technique has been highly succesful and it was used by Ilia Itenberg, in 1993, to provide counterexamples to the ninety year old Ragsdale conjecture.

Viro's construction of real smooth hypersurfaces uses regular (also called convex or coherent) triangulations of convex polytopes. Nevertheless, Viro's construction can also be applied as well to arbitrary triangulations. Are the combinatorial hypersurfaces coming from non-regular triangulations, still topological types of some real smooth hypersurfaces? In this talk we present current advances for the solution of this question. This is joint work with Frederick Wicklin.