CURRENT DIRECTIONS IN ALGEBRAIC COMBINATORICS 2003

FPSAC ’03 WHITE PAPER

Content:

1. Introduction

2. Enumeration

3. Statistical physics

4. Discrete probability

5. Bioinformatics

6. Quantum analogues

7. Non-commutative and non-symmetric functions

8. Face numbers and algebraic shifting

9. Cluster algebras and the Laurent phenomenon

10. Hopf algebras

11. Smoothed analysis

1. Introduction

The field of algebraic combinatorics has developed rapidly in recent years and is rich in connections with other areas, within mathematics as well as with physics, computer science, bioinformatics and other sciences. This activity and breadth is well represented at the annual FPSAC conferences, the most recent one taking place in Vadstena, Sweden, in June 2003.

Our aim here is to highlight some of the recent progress, capture some of the most important current directions, and try to delineate some of the emerging trends in algebraic combinatorics. This document was prepared, based on discussions at the FPSAC’03 conference, by an ad hoc committee consisting of Nantel Bergeron, Anders Björner, Mireille Bousquet-Mélou, Art Duval, Kimmo Eriksson, Christian Krattenthaler, Alain Lascoux, Svante Linusson and Richard Stanley.

2. Enumeration

Enumerative questions are at the core of algebraic combinatorics. They are involved in almost all topics discussed in this document.

The subject of enumeration of (symmetry classes of) plane partitions and alternating sign matrices is a classical subject by now. It got a new twist by the recent observations that plane partitions can be seen as rhombus tilings and that alternating sign matrices are in bijection with configurations in the intensively studied six vertex model of statistical mechanics. While many of the originally conjectured results are proved by now (by Andrews, Kuperberg, MacMahon, Mills–Robbins– Rumsey, Proctor, Stanley, Stembridge, Zeilberger), the understanding of this circle of problems is still very incomplete, particularly for the alternating sign matrices: the fact that there are still several conjectures unproved (such as the conjecture about the q-enumeration of totally symmetric plane partitions, or the conjectured enumeration formulas for three symmetry classes of alternating sign matrices) implies that we are still missing some important enumeration techniques which would lead to solutions of these problems. This is particularly true for the alternating sign matrices, where the solutions of the problems so far always contain a substantial guessing part. Second, there is still no understanding at all what plane partitions (rhombus tilings) and alternating sign matrices (six vertex model configurations) have to do with each other, although, empirically, the connection is “obvious” from comparison of the (proven or conjectured) enumeration results. Here, it seems, a new, fundamental bijection has to be found.

Finally, new mysteries have arisen recently in work by mathematical physicists (Razumov, Stroganov, de Gier, Batchelor, Nienhuis) on the XXZ spin chain: the ground states of certain Hamiltonians seem to be given by the numbers of configurations in the O(1) loop model (another disguise of six vertex model configurations), but there is no understanding at all why. It is however obvious that some very intriguing combinatorics must lie behind these phenomena.

3. Statistical physics

The field of physics known as statistical physics aims at predicting the behavior of macroscopic objects from the description of the interactions between their particles at a microscopic scale. The models of statistical physics simplify these interactions by assuming that the particles live on a regular grid and are only subjected to nearest-neighbor interactions. Solving a model means computing its partition function, which enumerates all possible configurations of particles according to their energy: hence, models of statistical physics are actually problems in enumerative combinatorics.

During a few decades, the main consequence of this connection was that many physicists were doing combinatorics. We can cite the names of Hammersley, Fisher, Temperley, in the 50’s, for their work on self-avoiding walks (polymer models, in physics), or Kac and Ward for the first combinatorial solution of the most famous magnetism model, the Ising model.

Nowadays, the border between combinatorics and physics has been crossed many times by researchers from both fields. In particular, combinatorialists have realized that statistical physics is an extremely profound and motivating source of problems in enumeration. Let us cite a few recent examples that illustrate this fruitful interplay.

3.1. Statistical physics in high dimensions. For many models, it is believed that there exists a critical dimension, above which the system behaves like an unconstrained (or: mean-field, in physics terms) model. For example, large selfavoiding walks (SAW) are supposed to behave like large random walks in dimension 5 or more. It might seem surprising to combinatorialists that high-dimensional models are sometimes more tractable than low-dimensional ones, but this is true: about 10 years ago, Hara and Slade proved the mean-field behavior of SAW in dimension 5 or more – whereas nothing similar is known in smaller dimension. Their technique involves a mixture of combinatorial and analytic arguments, and is gradually being generalized to other models (lattice trees, percolation...)

3.2. Quantum gravity and statistical physics on planar maps. In 2D quantum gravity, the change in the geometry of the space is modelled by putting particles, not on the vertices of a regular grid, but on the vertices of a random planar map (a map is the embedding of a graph in the plane). Since the early 70’s, certain physicists have developped very effective (but usually non-rigorous) techniques, based on matrix integrals, to solve models on maps. Their results have sometimes a remarkably simple structure, which begs for a combinatorial understanding. This was done a year ago by Bousquet-Mélou and Schaeffer for the Ising model. A lot remains to be understood.

3.3. Alternating sign matrices, the 6-vertex model, and the XXZ spin chain. The intriguing story of these objects and related conjectures has already been told in the section about enumerative combinatorics. Let us simply underline that certain determinantal expressions found by physicists for the 6-vertex model were the key step in the first “simple” proof of the ASM-conjecture, and that the more recent conjectures relating ASM to a certain Markov chain are also due to physicists...

More examples could be added, for instance a very nice collection of results on the enumeration of perfect matchings of graphs (in physics language, dimer coverings) by Propp, Kenyon, Wilson et al. Let us conclude by mentioning a few simple “physics” results that still await a combinatorial explanation: the enumeration of 3D directed animals (Dhar) or the refined enumeration of 2D directed animals (Bousquet-Mélou) yield nice algebraic functions, but have only been obtained via an equivalence with certain gas models; a determinant related to meanders (Di Francesco et al.) admits a mysterious expression in terms of Chebychev polynomials; finally, why is the spontaneous magnetization of the 2D Ising model so simple?

4. Discrete Probability

Combinatorics and discrete probability theory benefit from each other in a variety of ways; some related to questions in physics, others not. In extremal combinatorics, the so-called probabilistic method, which goes back to Erdős, continues to be enormously useful. In the other direction, combinatorial arguments often form the core part of proofs in various parts of probability, such as in large deviations theory, percolation theory, and the study of systems with spatial interaction. A striking example is Smirnov’s celebrated breakthrough for establishing conformal invariance in two-dimensional critical percolation. The talk by Olle Häggström at the FPSAC gave other interesting examples when the combinatorial properties of graphs and lattices are crucial to what can be said for problems in the above-mentioned fields. One of the satellite conferences to the European Congress of Mathematics 2004 has “combinatorial methods in statistical mechanics” in the title. It is a topic of rising interest.

During the last decade we have seen a growth in problems that have interested researchers across disciplinary boundaries. A good example is the Random Assignment Problem (a.k.a. random bipartite matching) studied by researchers from optimization, statistical mechanics, probability and combinatorics. In short it is the problem of deciding the size of a minimal assignment when the entries in the matrix are random variables. A fascinating conjecture from 1998 by the theoretical physicist Parisi giving the exact answer 1 + 1/4 + 1/9 + ⋯ + 1/k^{2} in the case of exponentially distributed random variables with mean 1 in a k × k matrix has inspired much of the further work. The conjecture was proved simultaneously by two independent groups in March 2003. The most general of these solutions (due to Linusson and Wästlund) uses algebraic-combinatorial tools, such as the Möbius function of a partially ordered set, at the heart of its discovery.

5. Bioinformatics

Modern biology is being reshaped in the post-genomic era, and its new basic building blocks are combinatorial in nature, such as genomes (with their finer structure of chromosomes, genes and DNA-sequences), the genetic code, protein structures, protein-protein interactions, and phylogenetic trees. It is by now wellknown that there are interesting applications of combinatorial methods within the rapidly growing field of bioinformatics/computational biology. Although some very good combinatorialists have entered the field, as yet it has attracted many more statisticians and computer scientists. For this reason FPSAC ’03 devoted a special session to combinatorial problems in bioinformatics.

There are two main directions of research in bioinformatics that are captured by the words evolution and function. In evolutionary bioinformatics we already see combinatorialists helping answer fundamental questions about the tree of life and the mechanisms of evolution. At FPSAC ’03 there were reports of recent work where classical concepts in algebraic combinatorics (such as edge labelled trees or the characters of the symmetric group) turned out to be important tools for making progress on questions in this area. Without doubt this development will continue for the next decade, as the increasing amount of data makes the biologists refine or revise their questions and hypotheses.

On the other hand, the area of functional genomics still very much awaits the breakthrough of combinatorial methods, e.g. to predict function (via 3D-structure) of proteins directly from their sequences of amino acids, to understand the interactions of proteins in the cell, and to make sense of amassing micro-array data.

6. Quantum analogues

An important recent development in algebraic geometry has been the development of “quantum analogues” of the cohomology rings of flag varieties. In particular, the quantum cohomology ring QH(Gr_{kn}; ℂ) of the Grassmann variety Gr_{kn} is related to a remarkable generalization of Schubert calculus due to Gromov and Witten which allows the computation of “3-point Gromov-Witten invariants.” These may be regarded as a q-analogue of the Littlewood-Richardson coefficients arising as intersection numbers in the classical case. A fundamental breakthrough in this area was achieved in 2002 by Alexander Postnikov. Ordinary Littlewood-Richardson coefficients appear in the expansion of skew Schur functions in terms of Schur functions. Skew Schur functions are defined combinatorially in terms of Young diagrams, which are certain planar arrays of boxes. Postnikov’s basic insight was that 3-point Gromov-Witten invariants have a similar description if one replaces planar Young diagrams with cylindrical and toroidal analogues. Using this idea Postnikov settled some open problems on 3-point Gromov-Witten invariants and discovered new symmetry properties that they satisfy. The subject of cylindrical and toroidal Schur functions has tremendous potential for further development.

7. Non-commutative and non-symmetric functions

7.1. Non-commutativity. Non-commutative methods have transformed our understanding of such classical fields as symmetric functions, determinants and minors, etc. For example, the classical Littlewood-Richardson rule for multiplying Schur functions becomes a straightforward consequence of the monoid structure that one can put on the set of Young tableaux. Non-commutative symmetric functions have a wider scope of applications than the commutative functions, e.g. they furnish new idempotents in Lie algebras. One can also define non-commutative extensions of quasi symmetric functions, and Schubert polynomials. Recent developments lead to similar algebras whose elements are other combinatorial objects like trees (Loday-Ronco algebra).

7.2. Non-symmetric functions. Symmetric functions theory is a topic in mathematics dating from the beginning of algebra. It has found applications in many diverse domains, including, most recently, Fock spaces in theoretical physics.

The theory of non-symmetric functions is much less developed, from the point of view of algebraic identities extending those satisfied by the different families of symmetric polynomials. The situation has changed during the last thirty years, motivated by algebraic geometry (flag manifolds, Schubert cycles, degeneracy loci) and representation theory (Demazure characters). One now has several families of polynomials extending Schur functions — Schubert polynomials, Grothendieck polynomials, key polynomials — which can be studied combinatorially independently of their geometrical interpretation. Properties of Schubert or Grothendieck polynomials are regularly presented at the FPSAC conferences since their start, this time by Yong at FPSAC 03.

The above-mentioned polynomials are also of much interest from the point of view of computer algebra. This is particularly true for algebraic computations of polynomials in several variables, where combinatorial manipulations of permutations can replace calculus with variables without the usual limitations on the number of variables. Schubert polynomials also occur as universal coefficients in Newton-type interpolation formulas.

Judging from the wide applicability of symmetric functions, one may predict with certainty that this field will develop in the near future and find new domains of application.

8. Face numbers and algebraic shifting

The study of face numbers for various classes of complexes continues to be a rich source of problems for algebraic combinatorics. Among the most interesting results of recent years is the proof by Ed Swartz that g-vectors of matroid complexes satisfy the same conditions as those of the g-theorem of simplicial polytopes. What is noteworthy is that his method does not depend on the hard Lefschetz theorem of a variety; this may open the door to further progress for other classes of complexes, notably triangulated spheres.

Other decisive progress has been made using the method of algebraic shifting. The first version of algebraic shifting to be studied was exterior algebraic shifting, so-called because it takes place in exterior algebra. Its most prominent success was in Björner and Kalai’s characterization of pairs of f-vectors and (homology) Betti numbers of simplicial complexes. More recent attention has been paid to symmetric algebraic shifting, which takes place in commutative algebra. Symmetric algebraic shifting has advanced quickly, helped by existing results on generic initial ideals, since the key step is the construction of a certain generic initial ideal.

Recently, Babson, Novik, and Thomas continued this trend by adapting “iterated Betti numbers” from exterior to symmetric algebraic shifting. These iterated Betti numbers are easy to compute for an arbitrary complex Γ from purely combinatorial information of the algebraically shifted complex Δ(Γ). Most intriguingly, certain “extremal” iterated Betti numbers determine extremal (free resolution) Betti numbers, which, in turn, determine a great deal of algebraic information, and which had been previously shown by Bayer, Charalambous, and Popescu to be preserved by symmetric algebraic shifting. Symmetric iterated Betti numbers and algebraic shifting thus reduce questions of the characterizations of many algebraic invariants to purely combinatorial questions about shifted complexes.

The differences and similarities between exterior and symmetric algebraic shifting remain unclear. Resolving this confusion will continue to be worthwhile for the near future.

Isabella Novik’s talk at FPSAC on characterizing face numbers of manifolds with symmetry featured a potentially very useful wrinkle on algebraic shifting. She replaced the completely generic matrix normally used in algebraic shifting by a matrix with certain entries specified, and others left generic as usual. Perhaps other specializations of the generic matrix will help algebraic shifting solve characterization problems for other special classes of simplicial complexes.

9. Cluster algebras and the Laurent phenomenon

The theory of canonical bases, originated by Lusztig, plays a key role in the representation theory and algebraic geometry related to semisimple Lie algebras. A completely novel combinatorial approach to the theory of canonical bases was found recently by Sergey Fomin and Andrei Zelevinsky and is currently under intense investigation. This approach is based on the concept of cluster algebras, a class of commutative rings with distinguished generating sets related in a combinatorial fashion. Closely related to cluster algebras is the subject of tropical geometry, which roughly speaking allows piecewise linear geometry to be replaced with subtractionfree manipulation of rational functions. As a bonus, Fomin and Zelevinsky realized that their techniques are applicable to some purely combinatorial problems that have been a source of much puzzlement since the 1980’s. These problems concern certain sequences, the first due to Michael Somos, whose terms are a priori rational numbers, but in fact turn out to be integers. More generally, certain sequences have terms that are a priori rational functions of several variables with complicated denominators, but whose denominators turn out to be monomials, an example of what Fomin and Zelevinsky call the Laurent phenomenon.

10. Hopf Algebras

Recent developments have linked distinct subjects within combinatorics, algebra, geometry, and theoretical physics thereby uncovering exciting new avenues for research. An old theme in algebraic combinatorics, initiated by Rota, is that many combinatorial objects possess natural multiplication and comultiplication structures. Enumeration and classification of these structures often give rise to an associated graded Hopf algebra. Many of these Hopf algebras of combinatorial objects (combinatorial Hopf algebras) possess important structures. The FPSAC talk by A. Lascoux reaffirmed the importance of comultiplication in algebraic combinatorics. As another example, Connes and Kreimer show that a Hopf algebra of rooted trees encodes renormalization in quantum field theory. Loday and Ronco show a Hopf algebra of planar binary trees has interesting operadic structure. Recent work of Ehrenborg, Bergeron, Sottile, Aguiar, and many others, give a natural Hopf morphism from any combinatorial Hopf algebras to the Hopf algebra of quasi-symmetric functions Qsym. This morphism arises from a universal property of the Hopf algebra Qsym as a terminal object in the category of graded Hopf algebras equipped with a zeta-function. In particular, many enumerative combinatorial invariants (among them flag f-vectors, Littlewood-Richardson coefficients, and chromatic symmetric polynomials) are obtained from this universal property. In light of this, the Hopf algebra Qsym, its generalization and its sub-structures are bound to play a very important role in algebraic combinatorics.

The connections uncovered between combinatorial Hopf algebras suggest a number of exciting possibilities. This includes a unified approach to positivity questions in different realms of enumerative combinatorics or using these results as a bridge to transfer ideas and techniques between these different realms. For example, both the Schubert calculus and polytope/poset theory have important open positivity questions and well-developed techniques to study these.

The work of Sagan and Rosas at this FPSAC suggested a new generalization of Qsym. As well, Ehrenborg suggested a new construction (which can be rephrased in Hopf algebraic language) to generate inequalities of g-vectors. Hugh Thomas presented maps between important lattices. These induce morphisms between related Hopf algebras. Finally, related to some of the combinatorial Hopf algebras is the study of their invariants. This gives some interesting space related to geometry. At least two presentations gave us further generalizations to consider. First, the poster of Aval presented quasi-invariants and super covariants. Second, the talk of Biagioli and Caselli gave the Hilbert series of some invariant algebras.

11. Smoothed analysis

The theory of algorithms has been challenged by the existence of remarkable algorithms, in particular the simplex method, that work well in practice but whose theoretical analysis is negative or inconclusive. The root of the problem is that algorithms have traditionally been measured in two ways: worst-case behavior or average behavior. In both situations, the analysis deals with instances of the algorithms that may differ widely from what actually arises in practice. A spectacular breakthrough in the analysis of algorithms was achieved by Daniel Spielman when he introduced a third method of analyzing algorithms, known as smoothed analysis. In smoothed analysis, the performance of an algorithm is measured under slight random perturbations of arbitrary inputs. A major result of Spielman’s is that the simplex algorithm has polynomial smoothed complexity. Numerous other fundamental algorithms have subsequently been shown to also have polynomial smoothed complexity, and the area of smoothed analysis has become one of the most active subjects in the theory of algorithms.