Richard P. Stanley Seminar in Combinatorics

Known proofs of the Four-Color Theorem consist of two steps - reducibility and discharging. While the discharging part is essentially human-checkable, the reducibility part is far from it. Reducibility is a useful technique that allows one to deduce that certain configurations cannot appear in a minimal counterexample, but it lacks a general theory.

Related notions of reducibility have been developed for the cycle double cover conjecture of Seymour and Szekeres and the 5-flow conjecture of Tutte. To settle these conjectures completely using this technique one would need the reducibility of an infinite sequence of configurations, and therefore at least a modest theory of reducibility.

We explain the technique of reducibility and discuss new results pertaining to the Four-Color Theorem and the 5-flow conjecture. This talk is based on joint work with Robin Thomas.

In the 1970's Zaslavsky initiated the modern study of hyperplane arrangements. For a central hyperplane arrangement he showed evaluating the characteristic polynomial at -1 gives the number of regions in the complement of the arrangement, whereas for an affine arrangement evaluating at +1 gives the number of bounded regions in the complement. For central arrangements Bayer and Sturmfels proved its flag f-vector can be determined by the intersection lattice. Billera, Ehrenborg and Readdy make this map explicit using coalgebraic techniques.

We extend the Billera-Ehrenborg-Readdy omega map to affine and toric hyperplane arrangements. For toric arrangements, we also generalize Zaslavsky's fundamental results on the number of bounded and unbounded regions. We believe these results hint at a wealth of problems involving regular subdivisions of manifolds. I will indicate a few of these directions.

This is joint work with Richard Ehrenborg and Michael Slone.

Consider the association scheme of the n-cube, with vertex set X={0,1}^n and relation R_i={(x,y): d(x,y)=i} where d denotes Hamming distance. The adjacency matrix of the n-cube generates a Bose-Mesner algebra, and if we extend this algebra by the diagonal matrix with (x,x)-entry n-2d(0,x), we obtain the Terwilliger algebra of the n-cube. This can also be viewed as the algebra of matrices that commute with the coordinatewise action of the symmetric group S_n on X.

A few years ago, the effort to find upper bounds for the size of a binary error-correcting code seemed to come to an impasse. A. Samorodnitsky proved that the optimum of Delsarte's linear program could never be equal to (or even close to, asymtotically) the Gilbert-Varshamov lower bound. The present talk is one of several efforts to bring new tools to the task of deriving upper bounds. (A closely related result, due to A. Schrijver, made headlines in 2004.) We apply some basic representation theory to describe all of the extreme rays of the positive semidefinite cone of the Terwilliger algebra. These are in one-to-one correspondence with all irreducible S_n-submodules of the module {R}^X. As a result, we obtain explicit linear inequalities which can be appended to Delsarte's system of inequalities (the "linear programming method") to improve overall upper bounds.

We illustrate our technique by extending work of de Klerk and Paschnik. They applied semidefinite programming to bound the size of a subset C of X having d(x,y) \neq n/2 for all x,y in C. Our approach is an iterative one, beginning with Delsarte's linear programming problem and adding inequalities based on a Lagrange multiplier analysis of the current optimal solution.

Based on joint work with Terry Visentin, University of Winnipeg.

A family of monomial bases of the Garsia-Haiman modules for hook shapes is presented, including k-analogues of the classical descent and Artin bases for the coinvariant algebra of type A. An explicit formula for the S_n-action on the k-th descent basis is given, and combinatorial decomposition rules, which extend a classical result of Lusztig and Stanley, are deduced. Relations with recent works of Haglund, Haiman, and Loehr will be mentioned.

Joint work with Ron Adin and Jeff Remmel.

Analogous to the theory of conservative vector fields, vertex colorings of graphs can be represented up to constant by edge functions that sum to zero around every cycle. More generally, one can assign arbitrary real intervals to the edges of a graph, defining a box in the space of edge functions, and ask if any function in this box sums to an integer around every cycle. The chromatic number of a graph, and generalizations such as the circular chromatic number and the cyclic group chromatic number, can be determined by knowing which such integer programs are feasible. A dual theory applies to flows.

Following in a recent tradition of understanding integer programs through toric algebra, we relate the cycle and second cycle structure of a graph to the algebraic structure of a corresponding toric ring. An irreducible decomposition of this ring corresponds to the maximal lattice-free polytopes studied by Scarf et. al., which for us characterize the maximal infeasible integer programs on the graph. Chromatic information about the graph is encoded in the failure of the Cohen-Macaulay condition for this ring.

This is joint work with Maria Chudnovsky and Lindsay Piechnik.

The chromatic symmetric function of a graph, first studied by Stanley in 1995, is a much stronger invariant than the chromatic polynomial, but no one seems to be sure exactly how strong it is. In particular, Stanley's question of whether two non-isomorphic trees can have the same chromatic symmetric function remains unanswered, and seems to be quite hard. Recently, Matthew Morin, Jennifer Wagner and myself have made partial progress by proving that the chromatic symmetric function is strictly stronger than Chaudhary and Gordon's subtree polynomial. We've also identified some special classes of trees which really are determined by their chromatic symmetric functions. As an unexpected bonus, studying the chromatic symmetric functions of certain trees called "caterpillars" may have applications in protein sequencing.

I'll describe a new invariant of matroids that takes the form of a quasisymmetric function, then describe some of its pleasant properties. One is that it defines a morphism between two known combinatorial Hopf algebras. Another is that it helps answer a subtle question that arises in work of Kapranov, Lafforgue, Hacking, Keel, Tevelev and others: when does a matroid polytope decompose into smaller matroid polytopes? Knowledge of quasisymmetric functions will not be assumed.

This is joint work with Lou Billera and Ning Jia.

Sabidussi showed that any connected graph can be uniquely decomposed into prime factores up to isomorphism with respect to the Cartesian product of graphs. This gives a free commutative monoid structure on the set of unlabeled connected graphs, generated by the set of unlabeled prime graphs. As a consequence of Sabidussi's theorem, we count prime graphs using Dirichlet series. On the other hand, as it turns out, the prime graphs can be enumerated in terms of connected graphs using species theory under the notion arithematic product of species defined by Maria and Mendez. We shall take a quick look at how that could be done.

We define a class of algebraic systems which is similar to bialgebras and Hopf algebras. We call them positive involutive 2-algebras. One typical example is Hecke algebra. Algebraic combinatorics give many other examples. The problem is to imbed such algebras into a bilagebra (or Hopf algebra) as subobjects or to prove that there are no such dilations. There are at least two rigorous meanings of the notion of "subobject" of bialgebras. The simpliest examples of dilation will be done. The talk is based on the paper math.QA/0702486 in arXiv.

A poset operation called Rees product was recently introduced by Björner and Welker in their study of connections between poset topology and commutative algebra. Through our study of Rees products of posets, we discovered a remarkable q-analog of a classical formula for the exponential generating function of the Eulerian polynomials. The Eulerian polynomials enumerate permutations according to their number of descents or their number of excedances. Our q-Eulerian polynomials are the enumerators for the joint distribution of the excedance statistic and the major index. There is a vast literature on q-Eulerian polynomials that involves other combinations of Eulerian and Mahonian permutation statistics, but this is the first result to address the combination of excedance number and major index. Although poset topology led us to conjecture our formula, symmetric function theory provided the proof. We prove a symmetric function generalization of our formula, which yields other enumerative results. In our work we also establish a connection between the cohomology of the toric variety associated with the Coxeter complex of type A (studied by Procesi, Stanley, Stembridge, and Dolgachev and Lunts), and the homology of certain intervals in the Rees product of a (partially truncated) Boolean algebra and a chain, as modules for the symmetric group.

This is joint work with John Shareshian.

We consider the following packing problem. How many d-dimensional cubes of side length 2 can we pack into a d-dimensional torus of odd side length? In this talk we present some of the best known constructions, detail the connection between this packing problem and the problem of determining the Shannon capacities of graphs, and discuss some recent techniques for establishing upper bounds.

Given a finite set of points S in R^d, consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S and let G^d_n be a n x ... x n grid in Z^d. It is known that L(G^2_n) = 2n-1 and 4/3 n^2 - O(n) <= L(G^2_n) <= 3/2 n^2 + O(n). Kranakis et al. conjectured that, for all d >= 3, L(G^d_n) = d/(d-1)n^{d-1}\pm O(n^{d-2}). We prove the conjecture for d = 3 by showing the lower bound for L(G^3_n). For d = 4, we prove that L(G^4_n) = 4/3 n^3 \pm O(n^{5/2}).

For general d, we give new estimates on L(G^d_n), that bring us very close to the conjectured value. The new lower bound (1+1/d)n^{d-1} - O(n^{d-2}) improves previous result by Collins and Moret, while the new upper bound (1+1/(d-1))n^{d-1} + O(n^{d-3/2}) differs from the conjectured value only in the lower order terms.

For arbitrary point sets, we give a an exact bound on the minimum number of links needed in an axis-aligned path in traversing any planar n-point set. We also obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in R^d by an axis-aligned spanning path with a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm.

This is joint work with Sergey Bereg, Jit Bose, Ferran Hurtado, and Pavel Valtr

Let λ be a Young diagram, and e a positive integer. Given a node (i,j) of λ, we define its residue to be j-i (mod e), and we define the content of λ to be the multiset consisting of the residues of all its nodes. Now we say that two partitions lie in the same e-block if their Young diagrams have the same content. These notions all come from the modular representation theory of the symmetric group, where (if e is a prime) the partitions in an e-block are the labels of the Specht modules lying in an e-block of S_n. It is pretty well known that two partitions lie in the same e-block if and only if they have the same e-weight and e-core, and this makes e-blocks much easier to understand from a combinatorial point of view.

The same set-up applies to multipartitions, and has representation-theoretic importance. But the appropriate notions of weight and core for multipartitions are not so easy to come by. In this talk I'll explain my attempts to define and study these.

Building upon the work of Kalai and Adin, we extend the concept of a spanning tree from graphs to simplicial complexes. For all complexes K satsifying a mild technical condition, we show that the simplicial spanning trees of K can be enumerated using its Laplacian matrices, generalizing the matrix-tree theorem. As in the graphic case, replacing the Laplacian with a weighted analogue yields homological information about the simplicial spanning trees being counted. We find a nice expression for the resulting weighted tree enumerator of shifted complexes, by generalizing a formula for the Laplacian eigenvalues of a shifted complex to the weighted case.

This is joint work with Art Duval and Jeremy Martin.

In 1935, T. R. Dawson, the prolific composer of fairy chess problems, invented a little game now known as Dawson's Chess, involving only pawns on a 3xN chessboard. He invested considerable effort trying to find a perfect winning strategy, but was ultimately unsuccessful.

We now know that much of Dawson's difficulty arose from the winning condition he imposed on the game: whoever makes the last move loses. This is known as the misere play condition. The normal-play counterpart of Dawson's Chess---in which the player who makes the last move wins---was solved in 1956, but the original misere-play formulation remains an open problem, after more than seventy years.

This is no accident: games with the misere play condition tend to be vastly more difficult than games with the normal play condition (even when the rules are otherwise identical). As a result, many authors have dismissed the misere theory as essentially intractable.

However, a recent breakthrough, due to Thane Plambeck, has sparked renewed interest. Plambeck showed that much of the misere-play theory for a specific game G can be localized to a certain commutative monoid, the misere quotient of G. I will describe Plambeck's construction, and show how the misere quotient contains exactly enough information to recover a perfect winning strategy for G. Then I'll present misere quotients for several previously unsolved games and discuss what little we know about the general structure theory of misere quotients. Finally, I'll (hopefully) shed some light on just why no one has yet solved Dawson's Chess.

The study of Q-polynomial distance-regular graphs is an active area of research. Many important examples arise on the top fibres of certain meet semilattices, such as truncated Boolean semilattices and direct products of "claw semilattices".

In 2003, Brouwer, Godsil, Koolen and Martin introduced the width w and the dual width w* of a subset in a Q-polynomial distance-regular graph. They showed that w+w* is at least the diameter D of the graph, and that if equality holds then the subset has a lot of strong regularities. For graphs associated with nice semilattices, those subsets satisfying w+w*=D arise quite naturally within the semilattice structures, and they are expected to play a role in the classification of Q-polynomial distance-regular graphs.

On the other hand, recently it is turning out that the subsets with w+w*=D also play a fundamental role in e.g., coding theory. In this talk, I will briefly discuss some of the applications of the theory of these subsets. Topics include the Erdos-Ko-Rado theorem in extremal set theory, the Assmus-Mattson theorem in coding and design theory, and orthogonal polynomials from the Askey scheme.

Many algebro-geometric problems about moduli spaces eventually boil down to deep combinatorial problems. In this talk I will show, by using symmetric groups, how combinatorics natually arises when we study the loci of certain branched covers of elliptic curves in the moduli space of genus g curves. Most of the results and open problems will be stated in a purely combinatorial setting. I will also mention a geometric interpretation that provides surprisingly neat proofs for some equalities from enumerative combinatorics.

Dumitriu, Tetali and Winkler have described a "whirling tours" algorithm that computes the expected time for random walk on a tree to get from a designated starting vertex to a designated target vertex (and that incidentally always gives a whole number). I'll explain why their algorithm works by situating it in the context of the Eulerian walkers model (aka rotor-router walk) and the abelian sandpile model (aka chip-firing).

The slides are available at http://jamespropp.org/tour0.pdf.

One of the most exciting discoveries in the early nineties, due to Herbert Wilf and Doron Zeilberger, was finding closed-form expressions for various sums and integrals, and finding proofs for special classes of summation/integration identities can be efficiently and elegantly handled by the computer. In this talk we explore and highlight the Wilf-Zeilberger (WZ) method and show various applications of the method in combinatorics.

The subject of pattern avoiding permutations has its roots in computer science, namely in the problem of sorting a permutation through a stack. A formula for the number of permutations of length N that can be sorted by passing it twice through a stack (where the letters on the stack have to be in increasing order) was conjectured by Julian West, and later proved by Doron Zeilberger. Goulden and West found a bijection from such permutations to certain planar maps, and later Cori, Jacquard and Schaeffer presented a bijection from these planar maps to certain labeled plane trees.

We show that these labeled plane trees are in one-to-one correspondence with permutations that avoid the generalized patterns 3-1-4-2 and 2-41-3. We do this by establishing a bijection, that preserves 8 statistics, between the avoiders and the trees. Among the statistics involved are descents, left-to-right maxima and left-to-right minima for the permutations, and leaves and the rightmost and leftmost paths for the trees.

In connection with this we conjecture the existence of a bijection between avoiders and two-stack sortable permutations preserving at least four permutation statistics.

This is joint work (in progress) with Anders Claesson and Sergey Kitaev.

A family of symmetric polynomials arose in our study of an open problem regarding tableaux and Macdonald polynomials. We will discuss this problem and see how it led us to explicit combinatorial rules for calculating in both the homology and cohomology of the affine Grassmannian. Our results suggest an 'affine' tableaux approach to the Macdonald problem as well as enumerative geometric questions concerning certain Gromov-Witten invariants.

No background in Macdonald polynomials, geometry or Schubert calculus will be assumed.

Joint work with Lapointe and with Lam, Lapointe, and Shimozono

For this talk, it is best to think of a symmetric association scheme not as a highly regular edge-coloring of the complete graph, but as a finite set X of points on the unit sphere in R^m with the following property: for any polynomials f and g in R[t], there exists a polynomial f*g such that, for all x,y in X

\sum_{z\in X} f(< x,z>) g(<z,y>) = (f*g)(<x,y>)

where <.,.> is the standard dot product. The association scheme X is cometric (or "$Q$-polynomial") if we have deg f*g <= min(deg f, g) for all f and g.

Cometric association schemes were introduced in 1973 by Delsarte as formally dual to distance-regular graphs. Examples arise from spherical t-designs such as the minimum length vectors in the E_m lattice (m=6,7,8) or the Leech lattice, and also from extremal error-correcting codes and block designs. Bannai and Ito conjectured in 1984 that there are only finitely many (up to isomophism) cometric schemes in dimension m for each m and that, if the number of angles involved is sufficiently large, a primitive cometric association scheme must also be metric (i.e., it comes from a distance-regular graph).

In this talk, I will survey recent results of Suzuki, Suzuki and Cerzo, Muzychuk, Williford and Martin, and I will mention a lot of examples. Finally, I will present a potential approach to the first Bannai-Ito conjecture mentioned above.