Richard P. Stanley Seminar in Combinatorics

A matrix is totally positive (resp. totally nonnegative) if all its minors are positive (resp. nonnegative) real numbers. The first systematic study of these matrices was undertaken in the 1930s by F.R. Gantmacher and M.G. Krein. More recently, G. Lusztig discovered a surprising connection between total positivity and canonical bases for quantum groups, and extended the subject by defining totally positive and totally nonnegative elements for any semisimple group. We shall discuss some classical results about total positivity, and how to extend them to arbitrary semisimple groups. Most of the new results to be discussed were obtained jointly with S. Fomin.

Let ${\cal P}_1,\dots,{\cal P}_k$ be convex polytopes in $\mathbb{R}^n$ with integer vertices, and let $t_1,\dots,t_k$ be nonnegative integers. Define the ``Minkowski sum'' $$ t_1{\cal P}_1 +\cdots+t_k{\cal P}_k=\{t_1v_1+\cdots+t_kv_k\,:\, v_i\in{\cal P}_i\}. $$ The \emph{mixed lattice point enumerator} of $P_1,\dots,P_k$ is the function of $t_1,\dots,t_k$ defined by $$ F(t_1,\dots,t_k) = \#\left( (t_1{\cal P}_1 +\cdots+t_k{\cal P}_k )\cap\mathbb{Z}^n\right). $$ It was first shown by McMullen that $F(t_1,\dots,t_k)\in \mathbb{Q}[t_1,\dots,t_k]$. The function $F(t_1,\dots,t_k)$ contains a lot of interesting information about the ${\cal P}_i$'s, such as their volumes, mixed volumes, and Ehrhart polynomials.

We will discuss two recently discovered examples of mixed lattice point enumerators. The first (in joint work with A. Postnikov) is closely connected with Kostant's partition function for the root system $A_n$. The second (with J. Pitman) is closely connected with parking functions.

We explicitly compute the celebrated Robinson-Schensted-Knuth correspondence (RSK) between the set of the matrices with non-negative integer entries, and the set of the plane partitions. More precisely, in suitable linear coordinates on both sets, the RSK is expressed via minima of linear forms, i.e, in the piecewise-linear terms. In particular, we answer the following question by Curtis Grene: ``What shape corresponds to a given permutation under the Robinson correspondence? Our main tool in establishing these formulas is the quantum matrices and crystal bases. Based on the ideas of M. Kashiwara, we introduce the notion of free crystals, and build two such crystals on the set of all matrices with integer entries. The RSK is completely described as a canonical isomorphism between these two crystals.

Two interesting combinatorial objects having enumerative connections with (type-A) noncrossing partitions are the associahedron and permutations with certain pattern restrictions. We will describe type-B analogues of these objects, and several results relating them to type-B noncrossing partitions. We will discuss further properties which parallel those known for type A.

We can represent metrical, linear and other geometrical structure on a set by coloring the edges of the complete graph whose vertices are the elements of the set. For a metric space (X,d), we can color edges st and uv the same iff d(s,t) = d(u,v). If every two vertices determine a unique line, we can alternatively color edges st and uv the same iff s and t determine the same line as u and v. An automorphism permutes the vertices and the colors. Thus, for example, the similarities are the automorphisms for R^n with the Euclidean metric coloring and the affine transformations are the automorphisms for R^n with the linear coloring. Both of these groups of automorphisms are doubly transitive on the vertices. The classification of finite doubly transitive edge colored graphs is complete when the group of automorphisms contains a doubly transitive simple group. We will present the known results, partial results and conjectures with regard to this classification and consider its connections with other work.

Let A be a set of vectors in d-dimensional space V over the finite field. Define a random walk on V as follows: at each step move along a uniform vector in A. We show that mixing and cutoff of these random walks intimately related to properties of the random matroid process, corresponding to A. In case of the graphical matroids, cutoff phenomenon of random walks follows from the threshold in random subgraphs. We conclude by discussing a similar connection between random walk on a symmetric group generated by transpositions, and random graphs.

We prove that the Poincare polynomial $\pi({\cal A},t)$ of an essential, central three arrangement ${\cal A}$ is $(1+t) \cdot c_t({\cal D}_0^\vee)$, where ${\cal D}_0$ is the sheaf associated to the kernel of the Jacobian of ${\cal A}$, and $c_t$ is the Chern polynomial. This shows that a natural generalization of Terao's theorem on free arrangements also holds for all three arrangements. We also prove that for such an arrangement ${\cal D}_0^\vee$ is a locally free sheaf on ${\bf P}^2$, and describe an algorithm which computes the Chern polynomial from a free resolution of the Jacobian of the defining polynomial of ${\cal A}$.

Everything one needs to know about arrangements, sheaves, Chern polynomials etc. will be covered. Several examples will be given so that there is always a concrete object to keep in mind.

The theory of Macdonald polynomials (certain remarkable symmetric functions) leads to difficult and profound positivity conjectures, which remain unproven. The conjectured positive quantities are expected to describe irreducible character multiplicities in certain graded modules that Garsia and I constructed some time ago. The natural setting for studying these modules is the geometry of the Hilbert scheme of points in the plane. I will explain the geometric conjectures which imply the Macdonald positivity conjecture, and outline their connections with some other interesting conjectures such as the McKay correspondence and the conjectured Cohen-Macaulay property of the variety of pairs of commuting matrices.

For a simple Lie algebra g there is a ring homomorphism from the representation ring of its finite dimensional representations, to the ring of "level-restricted" representations that takes the usual tensor product to the fusion product.

We are interested in a $q$-analogue of the tensor product that is compatible with the level restriction map; here by $q$-analogue we mean a grading or filtration. Let g be of classical type. Affine crystal theory yields a natural grading of both the ordinary and fusion tensor product multiplicity, but at the cost of replacing the irreducible tensor factors with suitable representations (which outside of type A, no longer be irreducible).

In type A, Foda, Leclerc, Okado, and Thibon [FLOT] have defined a $q$-analogue of the level restriction map, a Z[q]-linear map (no longer a ring homomorphism) that specializes to level restriction at $q=1$. We show that this map sends the q-analogue of ordinary tensor product to the q-analogue of the fusion product.

Almost all of our proof works for classical type, where the FLOT map has a natural generalization. The only gap is a conjectural lemma on the grading, which is known to hold in type A.

Finally, in type A we prove a q-analogue of the level-rank duality for fusion product multiplicities in the special case where affine crystal theory applies, and propose its generalization for the q-analogue of tensor product multiplicity defined by Lascoux, Leclerc, and Thibon via ribbon tableaux.

This is joint work with Anne Schilling.

P.W. Kasteleyn gave an algorithm to count the perfect matchings in a planar graph and a graph on a torus using Pfaffians (similar to determinants) of a modified adjacency matrix of the graph. He stated that perfect matchings in a graph embedding on a $g$-holed torus could be enumerated by a linear combination of $4^g$ Pfaffians of differently modified adjacency matrices, but did not give the complete construction.

We give an explicit construction that not only does this, but also does it for graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a $g$-holed torus with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed by a linear combination of $2^{2g+1}$ (respectively, $2^{2g+2}$) Pfaffians. Together with the $g$-holed torus, these comprise all the compact boundaryless 2-manifolds.

As an application, we count the perfect matchings in an $m\times n$ grid on a M\"obius strip.

The problem of finding explicitly the number of ramified coverings of the sphere by a surface of genus g, with simple branch points, given degree and prescribed ramification over infinity is a classical problem in geometry. It is often referred to as the "Hurwitz Enumeration Problem."

From a combinatorial point of view, the problem is equivalent to counting the number of certain types of ordered transitive factorizations of a permutation into transpositions, a fact observed by Hurwitz in his 1895 paper.

Factorizations of permutations into transpositions also occur in the counting of embeddings of graphs, and therefore in connection with the moduli spaces of real and complex algebraic curves.

In this talk I will describe a combinatorial approach to the problem that used a "cut-and-join" analysis, the treatment of the formal partial differential equation that is obtained, and the way in which results conjectured by these means can be proved. I will also discuss a number of questions about certain moduli spaces that this combinatorial approach raises.

This material involves pieces of joint work, at different times, with Ian Goulden, John Harer, and Alek Vainstein. Preprints can be obtained from http://xxx.lanl.gov/ps/math.AG/9902009, AG/9902011 and AG/9902044. A related talk will also be given on March 1 in the Applied Math Colloquium which may serve as a more elementary introduction.

A locally finite point set (such as the set $Z^n$ of integral points) gives rise to a lattice of polytopes in Euclidean space taking vertices from the given point set. We develop the combinatorial structure of this polytope lattice and develop Euler-type relations for valuations on polytopes using the language of Moebius inversion. In this context a family of inversion identities is derived, generalizing classical relations of Euler, Dehn-Sommerville, and Macdonald. These identities also yield combinatorial formulas for valuations such as volume, the integral lattice point enumerator, and the Euler characteristic.

A general machine for constructing a large class of statistics on words will be desribed. These statistics, which have a certain recursive structure, are called {\it splittable}. The classical Mahonian statistics major index (maj) and inversion number (inv) are examples, as are more modern Mahonian statistics such as the "Z" statistic of Zeilberger and Bressoud, Denert's "den" and Rawlings' interpolating statistic, "r-maj".

I will explain how, and in what sense, the entire class of splittable Mahonian statistics is generated by the single statistic "inv". I will also describe other non-Mahonian statistics which have a similar recursive structure and conclude with some remarks about the extension of these ideas to other combinatorial objects.

Determining the maximum number of edges an $n$-vertex simple graph can have when it does NOT contain a fixed subgraph $H$ is one of the oldest and most-studied problems of Extremal Graph Theory. The value is called the {\it Tur\'an number} $ex(n;H)$. {\it Norm-graphs} were introduced in a paper by Koll\'ar, R\'onyai and the speaker to answer this question when $H$ is a complete bipartite graph with appropriate part-sizes.

In this talk we define norm-graphs and discuss some variations and generalizations of them. We obtain new sharp bounds for the Tur\'an number of complete bipartite graphs. Applications in Discrepancy Theory and Ramsey Theory will also be presented.

This talk presents joint work with Noga Alon and Lajos R\'onyai.

The theory of identities for hypergeometric series (which includes most binomial coefficient identities) is now well understood. Computer algebra systems can now recognize many identities as belonging to standard forms, and other identities can be proved mechanically, using the algorithms of Gosper, Wilf, Zeilberger, and others.

However, there are other types of identities that are not so well understood. An interesting class are identities for the Bernoulli numbers $B_n$, which are defined by the exponential generating function $$\sum_{n=0}^\infty B_n{x^n\over n!}={x\over e^x-1}.$$ (Similar identities exist for related sequences such as Genocchi numbers, Euler numbers, tangent numbers, and Eulerian polynomials.) These identities are of great interest in number theory and combinatorics, and there is quite a large literature on them, yet no systematic treatment.

In this talk I will try to bring some order to the theory of Bernoulli number identities. Here are examples of three different types of Bernoulli number identities that I will discuss:

Euler's identity: $$\sum_{i=0}^n{2n\choose 2i}B_{2i}B_{2n-2i}=-(2n-1)B_{2n}, \ n\ge2$$

Kaneko's identity:

\def\Bt{\tilde B} $$\sum_{i=0}^{n+1}{n+1\choose i}\tilde B_{n+i}=0, \hbox{ where $\tilde B_n=(n+1)B_n$}$$

Miki's identitiy: $$\sum_{k=2}^{n-2}\beta_k\beta_{n-k}-\sum_{k=2}^{n-2}{n\choose k}\beta_k\beta_{n-k} =2\beta_nH_n,\ n\ge 4,$$ where $\beta_k=B_k/k$ and $H_n=\sum_{i=1}^n 1/i$.

Since the work of K. Mahler about forty years ago, the binomial coefficient polynomials have played an important role in working with continuous functions on the p-adic integers which take p-adic values. The q-analogue of binomial coefficients will be shown to admit a similar role when q is a p-adic variable close to 1. Mahler's construction is recovered at q = 1, and several properties of his construction will be extended to the q-analogue.

In joint work with H. Pittie we have found a Pieri-Chevalley type formula for the K-theory of (generalized) flag varieties (i.e. Grothedieck polynomials). The formula generalizes the formula of Fulton and Lascoux, in particular, it generalizes the left and right key of a column strict tableaux. I will present our new formula, show how we were led to it with the affine Hecke algebra, demonstrate what it says about the combinatorics of Schubert polynomials, and explain how it is related to representation theory.

Using the Bidigare-Hanlon-Rockmore theory of random walk on the chambers of hyperplane arrangements, we define a notion of riffle shuffling for any finite Coxeter group or real hyperplane arrangement. We show that in the Coxeter case the resulting probability measures relate to enumerative problems about conjugacy classes in the finite groups of Lie type (with restrictions on the characteristic related to how the root hyperplane arrangement reduces mod p). We give open problems and mention another connection of type A,B card shuffling with Lie theory, namely the Poincare-Birkhoff-Witt theorem and splittings of Hochschild homology.

The topic of lattice polytopes appears in many places in mathematics:

- geometry (geometry of polytopes ,algebraic geometry with toric varieties , singularity theory),

-computing (linear programming)

-number theory (diophantine linear equations),and others

We will consider some particular recent developments:

-counting lattice points in lattice polytopes:the Ehrhart polynomial, explicit formulas for its coefficients, complexity ,dependance on the lattice;

-Triangulations and classification of lattice polytopes with respect to locally unimodular mappings;

-Lattice-free (empty )polytopes, asymptotic estimation for the width ( with dimension going to infinity),number of equivalence unimodular classes of lattice-free polytopes.

Posets containing no subposet isomorphic to the disjoint sums of chains $\mathbf{3+1}$ and/or $\mathbf{2+2}$ are known to have many special properties. However, while posets free of $\mathbf{2+2}$ and posets free of both $\mathbf{2+2}$ and $\mathbf{3+1}$ may be characterized as interval orders, no such characterization is known for posets free only of $\mathbf{3+1}$. We give a characterization of $(\mathbf{3+1})$-free posets in terms of their anti-adjacency matrices. Using results about totally positive matrices, we show that this characterization leads to a simple proof that the chain polynomial of a $(\mathbf{3+1})$-free poset has only real zeros.

The well known theorem of Borsuk is equivalent to saying that a certain characteristic class of a Z/2-representation is nonzero. Using other finite groups gives analogues. These are useful e.g. the prime power case of the "continuous" Tverberg theorem follows.

We present a basis of logarithmic series solutions at a point of maximal degeneracy to the Gelfand-Kapranov-Zelevinsky hypergeometric equations. These differential equations were studied by Batyrev, Hosono-Lian-Yau and Stienstra in the context of toric mirror symmetry. Our new construction is combinatorial and gives an explicit formula for the terms of such a series. Main ingredients are volumes of convex polytopes and shellings of triangulations. This talk is based on the material in Section 3.6 of the forthcoming book "Gr\"obner Deformations of Hypergeometric Differential Equations" (with M.~Saito and N.~Takayama). The current draft of our book is available at my homepage.

One of us will discuss how the WZ Theory Taketh and WZ Theory Giveth: The Incredible

Enhancement to Human INSIGHT and UNDERSTANDING that it Generated. The other one of us will give some recent examples of applications of the method. We leave you to guess which is which.

We explore the connections between parking functions and two of other sets of objects. First, we describe a bijection between parking functions and allowable pairs of permutations of a priority queue, which have been studied by Atkinson. The bijection preserves breakpoints, which are closely related to the idea of prime parking functions. We then provide an interpretation of the inversion enumerator for labeled trees using allowable pairs; Kreweras has previously interpreted the inversion enumerator for parking functions. We also obtain a generalization of the inversion enumerator using allowable pairs. Furthermore, we define valet functions, a variant of parking functions, and demonstrate a bijection between them and allowable pairs of permutations of a multiset.

We next discuss a symmetry in trees and its connection to parking functions. Gessel showed that the number of trees on $\{0,1,2,\ldots, n\}$ with $i$ descents and $j+1$ leaves equals the number of trees with $j$ descents and $i+1$ leaves. We provide a new proof of this by using recursions obtained from decompositions of trees. The method of proof leads to a generalization of a functional equation found by Knuth concerning trees in which every vertex is either a leaf or a descent. We use an analogous decomposition to show a symmetry in parking functions between descents and "disfavored spaces" of the parking function.

The results in this talk are part of the doctoral thesis of the presenter written under the direction of Professor Ira Gessel.