Richard P. Stanley Seminar in Combinatorics

We show that for large dimension d, the hard-core model on the integer lattice Z^d with all activities equal to lambda exhibits a phase transition when

lambda > C (log^3(d)/d)^(1/4)

More specifically:

We define the distance between any two points in the lattice to be the L^1 distance and say a subset I of the lattice is independent if no two points of I are adjacent (at distance 1).

Let B = [-N,N]^d be a large box in the lattice. For lambda >0, we consider the probability distribution on the independent subsets of B where each such I has probability proportional to lambda^|I|. Let p_e (resp. p_o) be the probability that I contains the origin given that all points on the boundary of B lying at an even (resp. odd) distance from the origin are in I.

There are many cases in which a naturally-defined sequence of graphs $G_1,G_2,\dots$ has the property that if one defines $f(n)$ as the number of perfect matchings of $G_n$ and extends the function $f$ in a natural way so that its domain contains all the integers, the resulting extension satisfies a reciprocity relation of the form $f(-n)=\pm f(n-c)$ for all $n$ (for some fixed integer $c$ and for some specific sign-rule).

I will survey known results of this type, some of which can be explained by Ehrhart reciprocity but most of which cannot.

For example, let $G_n$ denote the $m$-by-$n$ grid, with $m$ fixed. The associated numbers $f(n)$ satisfy a linear recurrence relation, and so may be extrapolated to negative values of $n$; these extrapolated values satisfy the relation $f(-n)=\epsilon_{m,n}f(n-2)$, where $\epsilon_{m,n}=-1$ if $m \equiv 2$ (mod 4) and $n$ is odd, and $\epsilon_{m,n}=+1$ otherwise. This result was proved algebraically by Stanley in 1985, but a new, combinatorial proof yields a generalization to the case where $G_n$ is the box-product of any finite graph $G$ with a path of $n$ vertices.

This is the first of two talks based on a joint paper with Sergey Fomin. I will concentrate on Y-systems, a particular class of birational recurrence relations associated with an arbitrary finite root system. These relations were introduced in 1991 by Al.B.Zamolodchikov, in connection with the theory of thermodynamic Bethe ansatz. We prove Zamolodchikov's conjecture that this system exhibits periodicity with period h+2, where h is the Coxeter number of the root system. Our proof is based on the study of a piecewise-linear version of the Y-system obtained from it by the "tropicalization" procedure. This version allows us to introduce a new family of simple polytopes (generalized associahedra) associated with root systems. These polytopes will be discussed by Sergey Fomin in the second talk of this series.

A map is a 2-cell embedding of a graph in a surface. The determination of the counting series for maps is a question that arises in combinatorics, in geometry, and in physics as a partition function. Tutte, for example. studied the enumeration of maps in the sphere as part of his attack on the Four Colour Problem.

In this talk I will discuss an algebraic approach to determining the counting series for maps in orientable surfaces and in all surfaces (including non-orientable surfaces) in terms of Jack symmetric functions. The indeterminate b in the Jack parameter a=1+b is conjectured to mark an invariant of rooted maps.

The counting series for maps with one vertex is central to the determination of the Euler characteristic of the moduli spaces of complex (b=0; Schur functions) and real algebraic curves (b=1; zonal polynomials). The complex case was treated by Harer and Zagier. If time permits I shall refer briefly to the conjectured combinatorial role of b in this context.

This is the second of two talks based on a joint paper with Andrei Zelevinsky, which was motivated by the theory of cluster algebras , on one hand, and by Zamolodchikov's periodicity conjecture for Y-systems, on another.

The presentation will be self-contained, and will focus on the second part of the title ("generalized associahedra").

We introduce and study a family of simplicial complexes which can be viewed as a generalization of the Stasheff polytope (a.k.a. associahedron) for an arbitrary root system. In types A and B, our construction recovers, respectively, the ordinary associahedron and the Bott-Taubes polytope, or cyclohedron. In a follow-up joint project with Frederic Chapoton, we present explicit polytopal realizations of these generalized associahedra. On the enumerative side, these constructions provide natural root system analogues to noncrossing/nonnesting partitions.

In the last decade several results have been found concerning lattice regions in the plane whose number of tilings by certain tiles is a perfect power or a near-perfect power. We review some of them and present new simple, unified proofs. We also discuss and generalize a conjecture due to Matt Blum on enumerating the tilings of a certain family of regions on the lattice obtained from the triangular lattice by drawing in all altitudes.

What is Combinatorics in 2002 and where are we going? The subject of combinatorics has been transformed immensely in the last fifty years. It has gone from being an recreational hobby to one of the major areas of mathematics today. In fact, Combinatorics is applied to almost all areas of mathematics: algebra, algebraic geometry, probability, topology, symplectic geometry, operations research, mathematical biology, as well as computational complexity, design and analysis of algorithm, and statistical physics.

In this discussion, we hope to clarify the role of Combinatorics in the present and future. The panel will consist of five people: Sara Billey (MIT), David Jackson (University of Waterloo/MIT), Igor Pak (MIT), Jim Propp (University of Wisconsin/Harvard) and Santosh Vempala (MIT). Dan Kleitman will moderate the discussion and Richard Stanley will act as the supreme arbitrator. Much of the time will be allotted to questions and opinions from the audience. Everyone is encouraged to participate in this lively debate.

In the usual game of 20 questions, one player tries to determine a hidden object by asking a series of "yes or no" questions. A number of real life search problems have this general form. However, in applications one is usually limited to a predetermined set of questions, and one is not required to determine the hidden object precisely, but rather only to determine the object up to some sort of equivalence.

For example: Suppose one has a communications network, and a storm (or a terrorist attack, or...) knocks out some of the arcs in the network. For each arc of the network, one may test "Is this arc still working?" (This is the predetermined list of allowable questions.) The goal may not be to determine the surviving network precisely, but instead to determine the answers to a small list of questions of the form "Is the network still connected?" "Is there still a direct connection between Point A and the Point B?", etc.

In the problems we examine, we will assume that one can complete the task if one is permitted to ask all of the allowable questions. The question we will aexamine is - Is it possible to do better? That is, can one complete the task without asking all of the allowable questions?

Our approach is to restate the problem in a more topological form. We will then define a new homology theory that captures the difficulty of solving this problem. The link between the homology theory and the original search problem is provided by a slight generalization of "Discrete Morse Theory."

Stanley-Reisner rings and affine semigroup rings are central concepts of combinatorial commutative algebra. For these studies, explicit descriptions of the local cohomology modules with supports in maximal monomial ideals are fundamental. In the Stanley-Reisner ring case, Hochster's formula gives a topological description. But recently, for affine semigroup rings, several authors investigated the case where the support ideal is not maximal. In this case, the local cohomology modules are neither noetherian nor artinian, but still have nice graded structure.

This talk will concern the local cohomologies of a Stanley-Reisner ring with supports in a general monomial ideal. A monomial ideal of a Stanley-Reisner ring associated to a subcomplex of an (abstract) simplicial complex. I will give a combinatorial topological formula for the multigraded Hilbert series, and in the case where the ambient complex is Gorenstein, compare this with a second formula that generalizes results of Mustata and Terai. The agreement between these two formulae is seen to be a disguised form of Alexander duality.

This is a joint work with V. Reiner and V. Welker.

The algebra of polylogarithms is the smallest C-algebra that contains the constants and that is stable under integration with respect to the differential forms dz/z and dz/(1-z). It is known that this algebra is isomorphic to the algebra of the noncommutative polynomials equipped with the shuffle product. As a consequence, the polylogarithms Li_n(g(z)), where the g(z) belong to the group of biratios, are polynomial on the polylogarithms indexed by Lyndon words with coefficients in a certain transcendental extension of Q : MZV, the algebra of the Euler-Zagier sums. The question of knowing whether the polylogarithms Li_n(g(z)) satisfy a linear functional equation is then effectively decidable up to a construction of a basis for the algebra MZV.

In the first part of this talk I will address some problems in classical invariant theory from a combinatorial point of view. Consequences of Schur-Weyl duality, the theory of symmetric pairs and Roger Howe's theory of dual reductive pairs will serve as tools to connect the combinatorial ideas with invariant theory.

During the second part of the talk, research done in collaboration with Thomas Enright will be described. This work is based on results of Thomas Enright, Roger Howe and Nolan Wallach concerning unitary highest weight representations. Specifically, we will see how these results provide a modern context for the Littlewood restriction formula (which is a branching rule for decomposing finite dimensional representations of GL(n) into irreducible representations of an orthogonal or symplectic subgroup). This context provides a stronger formulation of Littlewood's result. The results from the second part of the talk shed light on the problems addressed in the first part.

Few hundreds years ago, Waring asserted (without proof) that every atural number can be represented as the sum of few powers. More precisely, for every natural number k, there is a nutural number s such that every natural number n can be written as sum of s kth power (of non-negative integers). For instance, every natural number is a sum of 4 squares, 9 ubes and so on.

Waring's assertion has turn into one of the main research problems in number theory. It was first proved by Hilbert, and a little bit later by Hardy and Littlewood, using the circle method. Works on Waring's problem still continue even today.

About 20 years ago, Nathanson posed a question that whether one can represent all natural numbers using only "few" powrs (by few we mean a sparse subset of the set of all kth powers). May results have been obtained by Erdos, Nathanson, Zollner and Wirsing for the case k=2.

In this talk, we will solve Nathanson's question for general k. The proof is a combination of number theory, probablity and combinatorics and some of the tools arof independent interest.

We propose an approach to address data uncertainty for discrete optimization problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows to control the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0-1 discrete optimization problem on n variables, then we solve the robust counterpart by solving n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0-1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. Moreover, we show that the robust counterpart of an NP-hard $\alpha$-approximable 0-1 discrete optimization problem, remains $\alpha$-approximable. (joint work with Melvyn Sim)

A planar map is a proper embedding of a graph in the plane. W.T. Tutte gave in the 60's beautiful formulas for the number of (combinatorially distinct) planar maps with n edges but also for subclasses like triangulations, quadrangulations, etc. Some of these formulas were also found by physicists in the 70's. David Jackson recently discussed some algebraic aspects of this theory in this seminar (Feb. 20). We shall instead consider bijective approaches to enumerative and probabilistic questions.

First, I will present a bijective proof of Tutte's formulas, building on the cycle lemma used by Raney in his bijective proof of the Lagrange inversion formula. Second, following physicists, we shall put the uniform distribution on quadrangulations and view them as random surfaces. Bijections again allow to study the geometry of these random surfaces and lead to a surprising connection with a probabilistic process introduced by David Aldous (the Brownian snake constructed on a standard Brownian excursion). As a consequence the diameter (in graph theoretic sense) of a random quadrangulation with n vertices grows like n^{1/4}.

Complex groups generated by involutory reflections arise naturally in the modern theory of abstract regular polytopes. These groups preserve a hermitian form on complex n-space and are generated by n involutory hyperplane reflections. We are particularly interested in the case that the subgroups generated by all but a few generating reflections are finite (unitary) groups. For example, all the subgroups generated by n-1 reflections may be finite. We explain how the enumeration of certain finite universal regular polytopes can be accomplished through the enumeration of certain types of finite complex reflection groups, and describe all the finite groups and their diagrams which arise in this context. This is joint work with Peter McMullen.

A formula, due to Snapper, gives the number of 3-dimensional (0,1)-matrices with fixed plane sums as an inner product of certain characters of the symmetric group. Using this formula we give a criterion, in the spirit of the Gale-Ryser theorem, for deciding when such number is one. We also establish a conexion with the problem of determining the minimal components, in the dominance order, of the Kronecker product of two irreducible characters of the symmetric group.

In looking for ways of computing the multiplicity of the minimal components we are led to a one-to-one correspondence between 3-dimensional (0,1)-matrices and certain triples, which uses and generalizes the dual RSK-correspondence. One application of it is a combinatorial description of those multiplicities in terms of matrices.

The concept of hypergraph discrepancy provides a unified combinatorial framework for handling classical discrepancy problems from geometry and number theory. Since the discrepancy of a hypergraph can be small for somewhat arbitrary reasons, variants of hypergraph discrepancy have been introduced in the hopes of getting a better measure of the `intrinsic balance' of a hypergraph. Two such variants are linear discrepancy and hereditary discrepancy. Lov\'asz, Spencer and Vesztergombi proved that the linear discrepancy of a hypergraph \({\mathcal H}\) is bounded above by the hereditary discrepancy of \({\mathcal H}\), and conjectured a sharper bound that involves the number of vertices in \({\mathcal H}\). In this talk we give a short proof of this conjecture for hypergraphs of hereditary discrepancy 1. For hypergraphs of higher hereditary discrepancy we give some partial results and propose a sharpening of the conjecture.

A number of combinatorial problems with the symmetric group can be resolved using probabilistic methods. In this talk we discuss some of these of problems, including the following two:

1) Given a permutation s \in S_n, and a random conjugate t of it, what is the probability that s and t commute?

2) Given a word w(X,Y), what is the probability that two random elements x,y \in S_n satisfy w(x,y)=1?

Applications include recognition algorithms for finite groups, and a connection to Magnus's conjecture about a residual property of free groups. The talk assumes no group theoretic background and should be accessible to a general audience.

Finite combinatorial objects often come with notions of size and containment. It is natural to ask whether they can be constructed step by step in such a way that each object contains the last and is uniformly random among objects of its size.

For example: starting with a triangle drawn on the plane, can you add line segments two at a time so that at every stage you have a uniformly random triangulation of a polygon?

We will describe such processes for this and some more general structures related to Catalan numbers. (Joint work with Malwina Luczak, Cambridge.)

A graph coloring is called proper if no two nodes of the same color are connected by an edge. Deciding whether a graph has a proper coloring is a classical problem, of interest in Combinatorics and Computer Science.

In this talk we study the probability that a random graph on n vertices with average degree d has a proper 3-coloring. This probability decreases as d grows, and it is conjectured that it jumps from 1 to 0 as n tends to infinity, when d passes a threshold t of about 4.7. We survey known results on the subject and prove that t > 4.03. We also show that almost all 4-regular graphs are 3-colorable. The proof uses analysis of differential equations which arise in the study of a greedy heuristic algorithm for graph coloring.

This is joint work with Dimitris Achlioptas, and will appear at the Symposium on the Theory of Computing (STOC) 2002.

In 1994 Garsia and Haiman conjectured that the Hilbert series for the space of diagonal harmonic alternates can be described by a certain rational function $C_n(q,t)$. They showed that $ C_n(1,1) =c_n$, the $n$th Catalan number; that $C_n(1,q)$ satisfies the recurrence of the Carlitz-Riordan $q$-Catalan polynomial $C_n(q)$; and that $ q^{\binom{n}{2}}C_n(q,1/q)$ evaluates to the $q$-Catalan polynomial. Haiman used techniques from algebraic geometry to show that $C_n(q,t)$ is a polynomial. In 2000, Garsia and Haglund gave a combinatorial proof that $C_n(q,t)$ has nonnegative integer coefficients. The 1994 conjecture was confirmed by Haiman in 2001.

Garsia and Haglund's proof of nonnegativity gave a combinatorial interpretation of $C_n(q,t)$ as the generating series for two statistics $area$ and $dmaj$ defined on the set of Catalan paths of length $2n$. (A Catalan path is a lattice path from $(0,0)$ to $(n,n)$ which remains weakly above the line $y=x$, and which takes only horizontal and vertical steps.) After giving some background on the $q,t$-Catalan polynomial, I will extend the statistics $area$ and $dmaj$ to Schr\"oder paths: lattice paths from $(0,0)$ to $(n,n)$ which remain weakly above the line $y=x$, and which take horizontal, vertical, and diagonal steps. The generating series for $area$ and $dmaj$ over Schr\"oder paths having $d$ diagonal steps $S_{n,d}(q,t)$ defines a polynomial which is believed to be symmetric in $q$ and $t$. That is, $S_{n,d}(q,t)=S_{n,d}(t,q)$. I will discuss properties of $S_{n,d}(q,t)$ which support this conjecture.

A recent result in the representation theory of quantum groups describes a familty of finite-dimensional representations which, it turns out, are completely determined by combinatorial properties. The story of the conjecture and proof involves symmetric functions in a way appealing to both combinatorists and representation theorists.

Joint work with Ian Grojnowski.

The main object of the talk is to present some explicit formulas for expanding the product of certain Grothendieck polynomials in the basis of such polynomials. Grothendieck polynomials are representatives for Schubert classes in the K-theory of the variety of complete flags in the complex $n$-dimensional space; thus, they generalize Schubert polynomials, which are representatives for Schubert classes in cohomology. Our formulas are concerned with the multiplication of an arbitrary Grothendieck polynomial by one indexed by a simple transposition, and, more generally, by a cycle of the form $(i,i+1,...,i+p)$; in other words, we generalize Monk's and Pieri's formulas for Schubert polynomials. Our formulas are in terms of chains in a suborder of the Bruhat order on the symmetric group (known as k-Bruhat order) with certain labels on its covers. We deduce as corollaries A. Lascoux's transition formula for Grothendieck polynomials, and give a new formula for the product of a dominant line bundle and a Schubert class in K-theory; a previous formula of this type was given by W. Fulton and A. Lascoux, and later generalized by H. Pittie and A. Ram. Part of this work is joint with F. Sottile.

The representations of sl(3), crucial to the description of elementary particles (quarks, colour and all that), can be displayed completely explicity, over the integers, by studying remarkable polytopes in three dimensional space, called diamonds, and associated directed graphs.

No knowledge of Lie theory required.

A bijective map $r: X^2 \longrightarrow X^2$, where $X = \{x_1, \cdots , x_n \}$ is a finite set, is called a \emph{set-theoretic solution of the Yang-Baxter equation} (YBE) if the braid relation $r_{12}r_{23}r_{12} = r_{23}r_{12}r_{23}$ holds in $X^3.$ Each such a solution (we denote it by $(X;r)$) determines a semigroup $S(r)$ and a group $G(r)$ with a set of generators $X$ and a set of quadratic relations $R(r)$ determined by $r$. The problem of studying the set-theoretic solutions of YBE was posed by Drinfeld in 1990.

In this talk I shall discuss the relation between the set-theoretic solutions of YBE, and a special class of standard finitely presented semigroups $S_0$, called \emph{semigroups of skew polynomial type} which I introduced in 1990. In a joint work with Michel Van den Bergh we prove that the set of relations $R_0$ of each semigroup $S_0$ of skew polynomial type determines a (\emph{non-degenerate involutive square-free}) solution of YBE. The corresponding semigroup rings also present a new class of Noetherian Artin-Schelter regular domains. In connection with this, in 1996, I made the conjecture that for each such solution $(X;r)$ the set $X$ can be ordered so, that the relations determined by $r$ form a Groebner basis, and the semigroup $S(r)$ is of skew polynomial type. Using combinatorial methods, recently I verified the conjecture for $n \leq 31$. I shall also discuss the relation between my conjecture and a conjecture of Etingof and Schedler, and various cases in which I verify their conjecture for large $n$.