Richard P. Stanley Seminar in Combinatorics

A matrix is completely positive if it can be factored as A=BB^T where B is elementwise nonnegative. Such matrices arise in block designs and in statistics and are related to copositive matrices. Clearly if A is completely positive than it is doubly nonnegative, i.e. positive semidefinite and elementwise nonnegative. This necessary condition is not sufficient. If A is a nonnegative symmetric matrix and its comparison matrix is an M-matrix than A is completely positive. This sufficient condition is not necessary. In the talk I will describe qualitative conditions on the matrices (in terms of odd cycles in the associated graphs) under which the necessary condition is sufficient and the sufficient condition is necessary. I will also discuss the smallest possible number of columns of B in a factrization A=BB^T of a completely positive matrix.

Explicit description of representation-theoretic categories in terms of quivers had been a significant part of I.M. Gelfand's philosophy in the 60s and 70s. The problem of finding such a description for the BGG category 0, though partially solved by the historic breakthrough of the Kazhdan-Lusztig theory, defied the complete solution for about 30 years now.

In this talk we use our results on perverse sheaves to explain how this problem is now reduced to a combinatorial challenge of finding intertwiners between certain representations of the polynomial coinvariants of the Weyl group.

Our construction of perverse sheaves, or IC-modules, does not use the derived categories and t-structures and makes sense for a wide variety of stratified spaces including toric varieties, affine Grassmannians, and locally symmetric spaces.

Alex Postnikov recently gave a combinatorially explicit cell decomposition of the totally nonnegative part of a Grassmannian, denoted Gr_{kn}+, and showed that this set of cells is isomorphic as a graded poset to many other interesting graded posets. The main result of our work is an explicit generating function which enumerates the cells in Gr_{kn}+ according to their dimension. As a corollary, we give a new proof that the Euler characteristic of Gr_{kn}+ is 1. Additionally, we use our result to produce a new q-analog of the Eulerian numbers, which interpolates between the Eulerian numbers, the Narayana numbers, and the binomial coefficients.

In this talk I shall discuss some tantalising and deep connexions between algebraic combinatorics and algebraic geometry, from my perspective as an algebraic combinatorialist.

An expression for the number of ramified covers of the sphere (elementary branch points, with the exception of one point (infinity) with arbitrary ramification) was conjectured by combinatorial means. It was discovered by using Hurwitz's encoding of a ramified cover as a transitive factorisation of a permutation into transpositions, with certain conditions. I shall discuss some of the algebraic combinatorics that lies behind the conjectured expression.

It is believed that the structure of the above problem, the classical Hurwitz Problem, is just a shadow of the rich structure that is thought to reside in the "double Hurwitz problem" (two points, zero and infinity, over which there is arbitrary ramification). This is a more complex permutation factorisation problem, but methods of algebraic combinatorics can be used to provide strong evidence that double Hurwitz numbers are top intersections on a moduli space of curves with a line bundle (a universal Picard variety). I shall describe some of the combinatorial side of this research on double Hurwitz numbers.

This is joint work with Ian Goulden and Ravi Vakil.

The Arshon sequence was given in 1937 in connection with the problem of constructing a square-free sequence on a given alphabet, that is a sequence that does not contain any subword of the type XX, where X is any non-empty word over the alphabet. The question of the existence of such sequence, as well as the question of the existence of sequences avoiding other kinds of repetitions, were studied in algebra, discrete analysis, and in dynamical systems.

The Dragon curve (the paperfolding sequence) was discovered by physicist John Heighway and was described by Martin Gardner in 1978. It is defined as follows: we fold a sheet of paper in half, then fold in half again, and again, etc. and then unfold in such way that each crease created by the folding process is opened out into a 90-degree angle. The "curve" refers to the shape of the partially unfolded paper as seen edge on. It turns out, that the Dragon curve is related to the sigma-sequence, that was used by Evdokimov in 1968 in order to construct chains of maximal length in the n-dimensional unit cube.

The Peano curve was studied by the Italian mathematician Giuseppe Peano in 1890 as an example of a continuous space filling curve. The Peano infinite word is a discrete analog of the Peano curve.

Are there any similarities between the Arshon sequence, the Dragon curve, and the Peano infinite word in terms of combinatorics on words? In this talk, I will answer this question using some recent results.

Let X be a family of k-subsets of the set {1, ... ,n}, let |X| be the cardinality of X, and let G(X, mu) be the expected maximum weight of a subset from X when the weights of 1, ..., n are chosen independently at random from a symmetric probability distribution mu on the reals. In a sense, G(X, mu) measures how large X is; it behaves somewhat similarly to ln |X|. Moreover, G(X, mu) can be easily computed for a variety of combinatorially defined X, such as matchings, bases in matroids, etc. via standard combinatorial optimization algorithms, while counting |X| can be hard. It turns out that G(X, mu) provides the best approximation for ln |X| if mu is the logistic distribution. In this case, G(X, mu) is asymptotically equivalent to ln |X| as long as (ln |X|)/k grows. Thus our results imply some weak equivalence of counting (computing |X|) and optimization (finding the maximum weight of a subset in X for a given set of weights on the ambient space).

Some old problems in probability can be recasted in terms of relations between G(X, mu) and |X|: if mu is the Bernoulli measure, we get the classical isoperimetric inequality in the Boolean cube due to Harper and if mu is the symmetric exponential measure, we get an inequality for the supremum of a stochastic process due to Talagrand. In general, we show that for any symmetric measure mu, the minimum value of G(X, mu) on X of a given cardinality is attained when X is the product of two Hamming spheres in the Boolean cube.

This is joint work with Alex Samorodnitsky.

I plan to talk about both finite and infinite combinatorics of the following situation. A set of voters is to choose between two alternatives. If a majority of the voters chooses one alternative, then their choice wins. But if the vote is a tie, then the decision is made by a "tie-breaker" rule, which specifies which sets of half the voters are winning coalitions.

If the number of voters is finite, the results I'll discuss are mostly about fairness. To what extent can a tie-breaker treat all voters alike? Or even treat equal-sized (small) sets of voters alike?

If the number of voters is infinite, most of the questions from the finite case become trivial, but many new questions arise, which have no analog in the finite case. I'll discuss some questions about which sets of voters might hold the balance of power in "close" elections.

The adjacency matrix of a graph on n vertices is a 0-1 nxn matrix, with the (i,j) entry being 1, iff there is an edge between vertices i and j. Often, understanding the eigenvalues of the adjacency matrix sheds light on combinatorial properties of a graph. In a d-regular graph, the largest eigenvalue is d. If the absolute value all other eigenvalues is small, we say that such a graph is an expander. Optimal constructions of such graphs are known, but they rely on group representation theory. In this work we describe a simple, combinatorial construction that is close to being optimal.

A useful property of expander graphs is the so-called Expander Mixing Lemma, which bounds the deviation of the number of edges between two sets of vertices from what is expected in a random graph. We show a converse to this lemma, namely, that if the deviation is small then the graph is an expander. The implication is surprisingly strong, in comparison to other combinatorial properties (edge expansion, vertex expansion) which also imply a bound on the eigenvalues.

The key tool in the construction is a signing of the edges of a d-regular graph by +1 and -1. This yields a 2-lift of a graph - graph on twice as many vertices which is also d-regular. Getting an expander graph in this way reduces to finding a signing of a graph such that the spectral radius of the signed adjacency matrix is small. We show that for all d-regular graphs such a signing exists, and that if the graph we start from is an expander, then such a signing can be found efficiently.

Joint work with Nati Linial.

We shall discuss the construction problem for convex polytopes. Given the combinatorial structure of a simplicial polytope, there is an open condition on the lengths of its edges, such that there exist a polytope with edges of given lengths. Aleksandrov's theorem gives sufficient conditions for such a construction. The problem of explicitly constructing a polytope in Euclidean space is important and very difficult. From geometric point of view, it can be reduced to finding lengths of polytope's diagonals.

Algebraic relations between lengths of edges and lengths of diagonals (or any other metric invariant) of simplicial polyhedron is the principal tool in our study. Their existence is also the main result of our paper. As an example of our approach, we prove the conjecture of Robbins on the degrees of generalized Heron polynomials for an inscribed n-gon.

This is a joint work with Igor Pak.

Let $w$ be an element in the Weyl algebra (generated by two elements $D$ and $U$, with a commutation relation $DU-UD=1$.) The normal ordering problem is to find the normal order coefficients $c_{i,j}$ in the sum $w = \sum c_{i,j} U^i D^j$, where in each term the $D$'s are to the right of the $U$'s.

I'll present my proof that, for $w$ a word in the letters $D$, $U$, the normal order coefficients $c_{i,j}$ are rook numbers on the Ferrers board outlined by $w$.

This provides a new proof of the Rook Factorization Theorem---that the generating function of rook numbers on a Ferrers board, expressed in terms of falling factorials $x(x-1)...(x-k)$, completely factors into linear components.

The Rook Factorization Theorem, in turn, provides an easy algorithm to compute the normal order coefficients of $w$.

I'll discuss a generalization to the normal ordering problem with elements in $q$-Weyl algebra (commutation relation $DU-qUD=1$).

The topological symmetry group of a finite, connected graph embedded in S^3 is the subgroup of the automorphism group of the graph consisting of those automorphisms which can be induced by a homeomorphism of the ambient sphere. These groups first appeared in chemistry, as a measure of the symmetries of molecules. We initiate the mathematical study of topological symmetry groups, and compare with Babai and Mani's work on the automorphism groups of planar graphs. My talk will be accessible to a general audience, and presents joint work with Erica Flapan, Ramin Naimi, and James Pommersheim.

We consider triangular holes on the hexagonal lattice and we study their interaction when the rest of the lattice is covered by dimers. More precisely, we analyze the joint correlation of these triangular holes in a "sea" of dimers. We determine the asymptotics of the joint correlation (for large separations between the holes) in the case when one of the holes has side 1, all remaining holes have side 2, and the holes are distributed symmetrically with respect to a symmetry axis. Our result has a striking physical interpretation. If we regard the holes as electrical charges, with charge equal to the difference between the number of down-pointing and up-pointing unit triangles in a hole, the logarithm of the joint correlation behaves exactly like the electrostatic potential energy of this two-dimensional electrostatic system: it is obtained by a Superposition Principle from the interaction of all pairs, and the pair interactions are according to Coulomb's law.

The proof involves combinatorics, hypergeometric functions, and Laplace's method for the asymptotics of integrals.

Historically, linkages appear as tools for tracing curves, they also have long been used in the mechanical engineering. One of the most famous examples is ``Watt parallelogram'', invented by James Watt to solve the problem of linking the piston of his steam engine to a point on the flywheel so that the straight line motion of the piston would convert to the rotation of the flywheel.

In this talk I will concentrate on three, purely mathematical, aspects of the theory of mechanical linkages:

1. Universality theorems for moduli spaces of mechanical linkages.

2. Applications of linkages to the representation theory of finitely- generated groups (Coxeter, Artin and 3-manifold groups).

3. Applications of polygonal linkages to the representation theory of Lie groups: Saturation theorems for the decompositions of tensor products of irreducible representations, etc.

A hypersurface M immersed in R^n (S^n, H^n, or another manifold with an affine connection) is locally convex if each point of M has an M-neighborhood which lies on the boundary of a convex body. Under what additional conditions does this guarantee that M, as a whole, is the boundary of a convex body?

This type of questions has been addressed at the end of the 19th century by Hadamard, E. Schmidt in the 1920s, A.D. Aleksandrov and van Heijenoort in the 1940-50s, Jonker & Norman, V. Arnol'd in the early 1970s, and more recently by Mehlhorn et al., Preparata et al., and the speaker.

We will present the strongest known criterion for global convexity for PL-surfaces in R^n and S^n. Recent results and conjectures for general surfaces will also be discussed. Some of the material for the PL-surfaces (but not all, and only for the PL-case) can be found at math.MG/0309370 on ArXiv.org.

The Temperley-Lieb algebra $TL_n(q)$ is a deformation of the symmetric group algebra coming from statistical mechanics. Some of its neat properties may be seen by relating it to the meander problem (counting non-intersecting closed planar paths through $2n$ fixed points on the line).

We will motivate a generalization $TL_n(x,y)$ of $TL_n(q)$ via an attempt to understand the Birkhoff-Lewis equations (which some hope may be used to give an algebraic proof of the four-colour theorem). $TL_n(x,y)$ is related to generalized Chebyshev polynomials and in a way is the greatest generalization we can make without losing many of the nice properties of $TL_n(q)$.

This talk is accessible to a general audience and presents joint work with David Jackson.

One of the most striking results in the theory of cluster algebras due to S.Fomin and A.Zelevinsky is the classification of cluster algebras of finite type, which turns out to be identical to the Cartan-Killing classification. This result can be stated purely combinatorially in terms of certain transformations ("mutations") of certain edge-weighted directed graphs ("diagrams"). Fomin and Zelevinsky proved that a diagram is of finite type if and only if it is mutation-equivalent to a Dynkin diagram.

We will discuss a complete solution of the following natural recognition problem: how to recognize whether a given diagram is of finite type without having to perform an unspecified number of mutations. We solve this problem by providing the list of all minimal infinite type diagrams. The list contains all extended Dynkin diagrams but also has 6 more infinite series, and a substantial number of exceptional diagrams with at most 9 vertices.

Combinatorial game theory is concerned with two-person perfect-information games, especially those classes of positions for which winning strategies can be stated explicitly, or at least proved to exist. The powerful mathematical methods (often requiring only paper and pencil, no computers) are most successful when applied to games whose positions often decompose into "sums". The many examples of such games include Nim, Dots and Boxes, Hackenbush (best played with colored chalk and erasures), Domineering (played with dominoes on a checkerboard), Konane (popular in ancient Hawaii), Amazons (invented less than fifteen years ago, but which has attracted a substantial following on the Internet), and Go (a popular Asian board game dating back several thousand years, and which supports nearly 2,000 active professionals today). The theory also applies very well to the fascinating new game called "Clobber", invented in Nova Scotia in the summer of 2001.

In many of these games, a mathematically defined "temperature" provides a numerical measure of the value of the next move. The extension of this notion to loopy positions, such as kos in Go, appeared in "Games of No Chance" in 1996. A subsequent extension, called "Environmental Go", includes a stack of coupons in addition to the Go board. This has led to fruitful collaborations between game theoreticians and professional 9-dan Go players. For the past four years, we have been developing methods and techniques which allow us to get rigorous analyses of the last 50 to 100 moves of some professional games, and we not infrequently discover fatal mistakes.

We will present a broad introductory overview of this subject, including a fascinating problem in which Go, chess, checkers, and domineering are all played concurrently.

Let F be a finite family of convex sets in n-dimensional Euclidean space. Helly's theorem asserts that if every n+1 members of the family has a point in common then there is a point in common to all members of the family.

Lovasz proved the following extension of Helly theorem:

Colorful Helly Theorem. Consider n+1 families of convex sets in R^n and suppose that for every choice of n+1 sets, one from each family there is a point in common to all these sets. Then one of the families is intersecting.

This innocent looking extension is quite deeper than Helly's original theorem and the associated Caratheodory-type theorem of Barany has many applications in discrete geometry.

Helly himself realized that in his theorem convex sets can be replaced by topological cells if you impose the requirement that all non-empty intersections of these sets are again topological cells. (Since the intersection of convex sets is also convex this requirement is automatically satisfied in the original geometric version.) Helly's topological version of his theorem follows from the later "nerve theorems" of Leray and others.

In the lecture I will present a topological version for Lovasz' colorful Helly theorem present a matroidal generalization and discuss related issues.

Suppose that a finite set of labeled points in the plane, a configuration, is given. Some pairs of those points, determined by a finite simple graph G, are to be kept at their same fixed distance apart. If the coordinates of the configuration are generic, then the question of whether the configuration is rigid is a purely combinatorial property of G, for which there isa polynomial-time algorithm. (A configuration is generic if there is no non-trivial integral polynomial satisfied by the coordinates.) But rigidity is a local property equivalent to there being only trivial infinitesimal motions satisfying the distance constraints. Is it possible to determine the more basic question as to whether there is any other non-congruent configuration in the planethat satisfies the distance constraints? If the distance constraints determine the configuration up to congruence, the configuration is called globally rigid, and if the configuration is assumed to be generic, the graph G is called generically globally rigid (in the plane). Necessary conditions for generic global rigidity in the plane are generic rigidity even when any edge is removed from G (generic redundant rigidity), It turns out that these conditions are also sufficient, which were conjectured by B. Hendrickson some years ago. The proof of this involves the calculation of the rank of a matrix (what I call a stress matrix), and a construction, due to T. Jordan and W. Sullivan, that builds G starting from the complete graph K(4) by operations that preserve the properties of being vertex 3-connected and generic redundant rigidity. and that G should be vertex 3-connected.

In the study of partition identities, generating functions make it possible for the theory of partitions to interact with $q$-series. This leads to the discovery of many interesting properties of partitions. On the other hand, some $q$-series identities can be studied and proved by employing partitions.

In this talk, I will discuss $q$-series identities that can be proved using partitions. In particular, in the latter portion of my talk, I will use partitions to give proofs of Ramanujan's $_1 \psi_1$ summation and the $q$-Gauss summation.

The Bruhat order is a partial ordering of the symmetric group S_n, first defined by Ehresmann, that arises naturally in algebraic geometry and representation theory. (It can be extended to any Coxeter group, but we only consider S_n.) A result implicit in the work of Chevalley and stated explicitly by Stembridge gives a formula for the number of maximal chains in S_n (under the Bruhat order), where the maximal chains are counted with a certain weight. The approach of Chevalley connects this counting with the degree of the complete flag variety F_n of type A_n-1. We consider the more general question of counting weighted saturated chains between any two elements u<v in S_n. There are close connectionw with the theory of Schubert polynomials and the degrees of Schubert varieties in F_n. This lecture is based on joint work with Alexander Postnikov.

Ultrametrics are metrics which satisfy d(ij) <= max {d(ik), d(jk)} for all triples ijk. These metrics arrise in various contexts including tropical geometry and clustering. Moreover, they are in correspondence to particular types of phylogenetic trees. I will discuss these motivations and the geometry of the space of all ultrametrics including why matching distances to trees is not so easy.

This talk is accesible to a general audience and all new ideas are joint with Lou Billera.

There will be two 30 min. talks with the following titles and abstracts:

Identities of Ehrhart polynomials arising from algebraic geometry, by Fu Liu

Mochizuki's work on torally indigenous bundles yields combinatorial identities by generating to different curves of the same genus. We rephrase these identities in combinatorial languages and strengthen them. The main result of our work is that given a certain way to construct a polytope from a connected trivalent graph, the odd values of the Ehrhart quasi-polynomials of this polytope is a single polynomial which depends only on the number of vertices and edges of the original trivalent graph. Then we are able to conclude that the number of dormant torally indigenous bundles on a general curve of a given type is expressed as a polynomial in the characteristic of the base field.

This is a joint work with Brian Osserman.

Ramsey Theory on the Integers, by Jacob Fox

In this talk, I will present classical results and new developments in Ramsey theory on the integers.

A system of linear equations is called partition k-regular if for every k-coloring of the positive integers, there exists a monochromatic solution to the given system of linear equations. A system of linear equations is called partition regular if it is partition k-regular for all k. Generalizing classical theorems of Schur and van der Waerden, Richard Rado classified the finite partition regular system of linear equations in his famous 1933 dissertation Studien zur Kombinatorik. Rado further conjectured that for all positive integers m, n, there exists k=k(m,n) such that every system of m linear equations in n variables that is partition k-regular must be partition regular.

Professor Daniel Kleitman and I recently proved the first nontrivial case, when n=3, of this conjecture, which is known as Rado's Boundedness Conjecture. In particular, if a, b, and c are fixed rational numbers, and if every 6-coloring of the nonzero rational numbers must have a monochromatic solution to ax + by + cz = 0, then every finite coloring of the positive integers must have a monochromatic solution to ax + by + cz = 0. I will discuss this result, as well as several recent conjectures whose proofs follow from our research. No prior knowledge of Ramsey theory is assumed.

Symmetric polyhedra have been investigated since antiquity. With the passage oftime, the concept of a polyhedron has undergone a number of changes which have brought to light new classes of highly-symmetric polyhedra. Coxeter's "Regular Polytopes" book and his various other writings treat the Platonic solids, the Kepler-Poinsot polyhedra and the Petrie-Coxeter in great detail, and cover what might be called the classical theory.

A lot has happened in this area in the past 30 years. In particular, around 1980, the class of regular polyhedra in Euclidean 3-space was considerably extended by Grunbaum and Dress, and an alternative approach to the full classification was later described by McMullen and the speaker.

This talk presents the complete enumeration of chiral polyhedra in Euclidean 3-space. Chiral, or irreflexibly regular, polyhedra are nearly regular polyhedra; their geometric symmetry groups have two orbits on the flags (regularpolyhedra have just one orbit), such that adjacent flags are in distinct orbits.There are several infinite families of chiral polyhedra, each with finite skew, or infinite helical, polygonal faces, and with finite skew vertex-figures. Their geometry and combinatorics are rather complicated.

In this talk we are going to discuss the structure of random van Kampen diagrams over finitely presented groups. Such diagrams have many remarkable properties which allow one to design new fast algorithms for the word, membership, and conjugacy problems in groups.

This is joint work with Alexei Myasnikov.