THE RESEARCH TRAINING NETWORK “ALGEBRAIC COMBINATORICS IN EUROPE”

C. Krattenthaler^{†}

Institut Girard Desargues, Université Claude Bernard Lyon-I 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France

               E-mail: kratt@euler.univ-lyon1.fr
                  WWW: http://igd.univ-lyon1.fr/~kratt

Abstract. I present four highlights from the scientific activities of the eight teams of the Research Training Network “Algebraic Combinatorics in Europe” in Bordeaux, Jerusalem, Linköping, Lyon, Marburg, Marne-la-Vallée, Roma, and Wien: • the proof of the combinatorial invariance conjecture for Kazhdan–Lusztig polynomials in an important special case; • the proof of the conjectures on the random assignment problem; • important progress on the Neggers–Stanley Conjecture on posets and the Charney-Davis conjecture on (certain) simplicial complexes; • new bijections between maps and trees with interesting applications to the Ising and the hard particle model on maps.

1. Brief introduction to ACE

The Research Training Network “Algebraic Combinatorics in Europe (ACE)” is a research training network in the 5th Framework Programme “Improving Human Potential and the Socio-Economic Knowledge Base” of the European Commission, running from September 1, 2002 to August 31, 2005, of which I happen to be the coordinator. The network consists of eight teams at

• the Université Bordeaux 1 (Scientist-in-Charge: Mireille Bousquet-Mélou);

• the Hebrew University of Jerusalem, the Weizmann Institute, Rehovot and the Bar Ilan University, Ramat Gan (Scientist-in-Charge: Ehud Friedgut);

• Linköpings Universitet, KTH Stockholm and Chalmers Tekniska Högskola (Scientist-in-Charge: Svante Linusson);

• the Université Claude Bernard Lyon 1 - CNRS Rhône–Alpes (Scientist-in-Charge: Christian Krattenthaler); before, until August 31, 2003: Université Louis Pasteur, Strasbourg (Scientist-in-Charge: Dominique Foata);

• the Université de Marne-la-Vallée (Scientists-in-Charge: Jacques Désarménien and Jean-Yves Thibon);

• the Philipps–Universität Marburg (Scientist-in-Charge: Volkmar Welker);

• the Università di Roma “Tor Vergata” (Scientist-in-Charge: Francesco Brenti);

• the Universität Wien (Scientist-in-Charge: Markus Fulmek).

† Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”.

The members of the Scientific Committee of the network are Anders Björner, Dominique Foata, Gil Kalai and Alain Lascoux.

In line with the goals of the 5th Framework Programme, the network trains pre- and post-doctoral researchers, by letting them work within the joint work programme of the eight teams. I refer the reader to the WWW site of the network at

                  http://igd.univ-lyon1.fr/~kratt/ace

for the various activities (the series of meetings Séminaire Lotharingien de Combinatoire, other meetings and conferences, summer schools, preprints, etc.) that are also open to the public outside of the network.

In the next section, I try to briefly indicate what one should understand by “Algebraic Combinatorics.” Then, in Section 3, I shall give a list of themes and objects that the teams of the network are interested in. Finally, in Sections 4–7, I present some of the advances that have been made by members of the network which I consider important.

2. What is “Algebraic Combinatorics”?

Clearly, this puts me in a difficult position since it is probably already difficult to “define” Combinatorics itself. Maybe it is preferable to quote “the” prototypical example, representation theory of the symmetric group (cf. [28, 29, 41]). This is an algebraic subject, the study of which leads necessarily to combinatorial objects like partitions (which label the irreducible representations), standard Young tableaux (for constructing bases of the irreducible representations), and to combinatorial algorithms like the Robinson–Schensted correspondence and Schützenberger’s jeu de taquin, which play an essential role in deeper studies of the subject. Let us content ourselves with

Algebraic Combinatorics concerns itself with the study of combinatorial problems arising from other fields and, on the other hand, with the application and use of techniques coming from other parts of mathematics to combinatorial problems,

assuming that there is some algebraic flavour on (at least) one of the two sides.

3. The research themes of ACE

The “definition” given in the previous section is clearly still rather wide. More specifically, the research of the network features three main directions: Enumerative Combinatorics (with permutations, words, plane partitions, alternating sign matrices, fully packed loop configurations, maps, trees, paths as objects of study), Combinatorics of Coxeter Groups and Related Polynomials (with symmetric functions, non-commutative symmetric functions, quasi-symmetric functions, and related combinatorial Hopf algebras, Kazhdan–Lusztig polynomials, Schubert polynomials, Macdonald polynomials as objects of study), and Geometric Combinatorics (with simplicial complexes, order complexes of posets, combinatorial homotopy and homology, discrete Morse theory, algebraic shifting as objects of study).

The following sections bring to the fore four highlights from the research done by the network.

4. Combinatorial invariance of Kazhdan–Lusztig polynomials

Here, I describe the recent advance that has been made by Brenti (Roma team), Caselli (post-doc in the network) and Marietti (Roma team) towards the proof of one of the outstanding conjectures on Kazhdan–Lusztig polynomials. For in-depth introductions into the subject, I refer the reader to [31, Ch. 7] and [6, Ch. 6]. I also point out the survey article [14].

The Kazhdan–Lusztig polynomials are polynomials P_{u,v}(q) in q, which are indexed by elements u, v of a Coxeter group W. For the sake of simplicity, for the most part of this section, I shall restrict my explanations to the case where W is the symmetric group S_{n} of permutations of {1, 2, …, n}.

To start with, I have to define the Kazhdan–Lusztig polynomials for the symmetric group S_{n}. Elements of S_{n} will be written in one-line notation σ = σ_{1}σ_{2} … σ_{n}, meaning the permutation

σ = (\begin{matrix}1 & 2 & … & n \\ σ_{1} & σ_{2} & … & σ_{n} \end{matrix}) .

The length of a permutation σ, denoted by ℓ(σ), is the number of inversions of σ, an inversion being a pair (i, j) with i < j but σ(i) > σ(j). For example, we have ℓ(2413) = 3, the inversions being the pairs (1, 3), (2, 3) and (2, 4).

The definition of the Kazhdan–Lusztig polynomials depends heavily on the Bruhat order on S_{n}, which I have to explain next. Let u, v ∈ S_{n}. Write u → v if there exists a transposition (i, j) (i.e., a permutation which interchanges the elements i and j but leaves fixed all other elements) such that

u ∘ (i, j) = v and ℓ(u) < ℓ(v).

For example, we have 2143 → 3142. Figure 1 shows the Bruhat graph for S_{3}, which is the graph containing all the relations → for S_{3}.

[figure: 123; 321; 213; 312; 132; 231]

Figure 1. The Bruhat graph of S_{3}

The Bruhat order then is the partial order on S_{n} which is the transitive closure of the relation →, that is,

u ≤ v

if u = v or else there exist w_{1}, w_{2}, …, w_{k}
such that u → w_{1} → ⋯ → w_{k} → v.

Figure 2 shows the Hasse diagram of the Bruhat order on S_{3} (which encodes the partial order ≤ in the way that u ≤ v if and only if u is lower than v and there is an upward path from u to v in the diagram).

We are now almost in the position to be able to define the Kazhdan–Lusztig polynomials for S_{n}, except that, first, we have to define the so-called R-polynomials. These

[figure: 123; 321; 213; 312; 132; 231]

Figure 2. The Bruhat order of S_{3}

are also polynomials in q indexed by pairs of permutations. The definition of the Rpolynomials R_{u,v}(q), u, v ∈ S_{n}, is recursive:

• R_{u,v}(q) = 0 if u ≰ v;

• R_{u,v}(q) = 1 if u = v;

• for any adjacent transposition s = (i, i + 1), we have

R_{u,v}(q) = \begin{cases}R_{us,vs}(q) & if ℓ(us) < ℓ(u), \\ qR_{us,vs}(q) + (q − 1)R_{u,vs}(q) & if ℓ(us) > ℓ(u). \end{cases}

In fact, it is not at all clear that this is a coherent definition, i.e., it is not clear whether there are indeed polynomials R_{u,v}(q) satisfying these (somewhat strange) properties. This is, however, a theorem due to Kazhdan and Lusztig [32] (see also [31, Sec. 7.5]).

The Kazhdan–Lusztig polynomials P_{u,v}(q), u, v ∈ S_{n}, are then defined by • P_{u,v}(q) = 0 if u ≰ v;

• P_{u,v}(q) = 1 if u = v;

• deg (P_{u,v}(q)) < \frac{1}{2}(ℓ(v) − ℓ(u)) if u < v;

• q^{ℓ(v)−ℓ(u)}P_{u,v} (1/q) = ∑_{u≤a≤v} R_{u,a}(q) P_{a,v}(q) if u ≤ v, which involves the R-polynomials in the last rule. Again, one can show that this is a coherent definition (see [32] or [31, Sec. 7.10 and 7.11]).

Clearly, in a first run, this is completely impossible to grasp. It seems therefore that we should better abandon this and do something else. (I almost hesitate to add that it is straight-forward to extend the above definitions of R-polynomials and Kazhdan–Lusztig polynomials for S_{n} to arbitrary Coxeter groups.)

However: Kazhdan–Lusztig polynomials for a Coxeter group W are instrumental in the construction of certain important representations of the Hecke algebra associated to W. This is, in fact, where these polynomials arose for the first time [32]. (In that context, the artificially looking definition of the Kazhdan–Lusztig polynomials becomes natural.) Furthermore, Kazhdan and Lusztig have shown in [33] that, for Weyl groups W, the coefficients of P_{u,v}(q) are dimensions of local intersection homology of the Schubert variety associated to W. (Thus, in particular, the coefficients of P_{u,v}(q) are non-negative in that case, which is not at all evident from the definition of P_{u,v}(q). For arbitrary Coxeter groups, this is still an open conjecture.) Furthermore, Kazhdan– Lusztig polynomials appear also in the theory of Verma modules (see, e.g., [4], [19]), the algebraic geometry and topology of Schubert varieties (see, e.g., [33], [34], [6]), canonical bases ([27], [50]), and immanant inequalities ([30]).

Thus, these complicatedly defined polynomials are of fundamental importance in representation theory, Schubert calculus, and related areas. In particular, it is of greatest interest to study their properties, because this would then have immediate implications in representation theory, Schubert calculus, etc. In this regard, over 20 years ago Lusztig (in private) and Dyer [26] made the following surprising invariance conjecture.

Conjecture 1. P_{u,v}(q) depends only on the combinatorial structure of the interval [u, v] := {x : u ≤ x ≤ v}; that is, given two Coxeter groups W and W′, if u, v ∈ W and u′, v′ ∈ W′, and if [u, v] ≅ [u′, v′] as partially ordered sets (posets), then

P_{u,v}(q) = P_{u′,v′}(q).

For example, if W = W′ = S_{4}, then the intervals [1234, 3142] and [1234, 4123] are isomorphic as posets, as is shown in Figure 3, and indeed one can verify that P_{1234,3142}(q) = P_{1234,4123}(q) = 1.

[figure: 1234; 2134; 1243; 1324; 2143; 3124; 1342; 3142; 1234; 2134; 1324; 1243; 3124; 2143; 1423; 4123]

Figure 3. The intervals [1234, 3142] and [1234, 4123]

Conjecture 1 has been shown by Brenti, Caselli and Marietti [16] for the important special case where u = e and u′ = e′, e and e′ denoting the identity elements in W and W′, respectively. That is, we have the following theorem.

Theorem 2. For any Coxeter group, the Kazhdan–Lusztig polynomial P_{e,v}(q) depends only on the poset structure of [e, v].

Remark. For the case of W = W′ = S_{n}, this was proved by Brenti [15]. Independently, du Cloux [22] showed this for finite and affine Coxeter groups. Furthermore, Delanoy [24] proved it for simply-laced Coxeter groups.

The proof of Theorem 2 begins with the observation that it suffices to show the claim for the R-polynomials, i.e., to show that if x, y ∈ [e, v] then R_{x,y}(q) depends only on the poset structure of [e, v]. This follows directly from the definition of the R- and the Kazhdan–Lusztig polynomials.

To accomplish the latter, the crucial idea is the idea of a special matching introduced in [15]. To motivate this idea, let us recall that, given s = (i, i+1) such that ℓ(vs) < ℓ(v), the map

x ↦ xs  (4.1)

defines a matching of the elements of [e, v] with the property:

if x ◁ y and xs ≠ y, then xs ≤ ys.  (4.2)

(Here, x ◁ y means that x < y and there is no z with x < z < y.)

Here is the definition of a special matching. As before, we view a matching as a fixedpoint free involution, i.e., as a function M without fixed points such that M(M(x)) = x for all x.

Definition. A matching M is called special if for all x and y we have:

if x ◁ y and M(x) ≠ y, then M(x) ≤ M(y).  (4.3)

The reader should note the analogy between (4.2) and (4.3). In particular, the map (4.1) is a special matching.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18]

Figure 4. A lower interval in a symmetric group

In order to give an example, let us consider the poset given in Figure 4 (which is indeed a lower interval [e, v] in a Coxeter group). Then the pairing {{1, 2}, {3, 7}, {4, 9}, {5, 14}, {6, 12}, {8, 13}, {10, 15}, {11, 17}, {16, 18}} defines a special matching.

What Brenti, Caselli and Marietti manage to prove is the following theorem, which “generalizes” the original definition of the R-polynomials given earlier.

Theorem 3. Let W be a Coxeter group, v ∈ W, and let M be a special matching defined on the interval [e, v]. Then

R_{u,v}(q) = \begin{cases}R_{M(u),M(v)}(q) & if M(u) ◁ u, \\ qR_{M(u),M(v)}(q) + (q − 1)R_{u,M(v)}(q) & if M(u) ▷ u. \end{cases}

Theorem 3 implies immediately the Invariance Theorem 2.

5. The random assignment problem

The purpose of this section is to report the solution of the random assignment problem by Linusson and Wästlund (Linköping team), the origins of which lie in conjectures by Mézard and Parisi [37, 39].

Let M be an n×n matrix of non-negative real numbers. An assignment is a selection of entries of M, such that we take exactly one from each row and each column. A minimum assignment is an assignment in which the sum of its entries is minimal. Figure 5 shows a 4 × 4 matrix, together with an assignment (with sum of entries equal to 19), and a minimum assignment (with sum of entries equal to 6). (Readers familiar

3 1 4 2 2 5 7 3 1 3 1 5 2 4 1 6  3^{}1 4 2 2 5 7^{}3 1 3 1 5^{} 2 4^{}1 6  3 1^{}4 2 2 5 7 3^{} 1^{}3 1 5 2 4 1^{}6

Figure 5. A matrix, an assignment, and a minimum assignment

3 1 4 2 4 2 5 7 3 1 1 3 1 5 6  3 1 4 2 4 2 5 7 3 1^{} 1^{}3 1 5 6

Figure 6. A rectangular matrix, and a minimum 2-assignment

with graph theory and combinatorial optimization will realize that finding the minimum assignment in an n × n matrix M is equivalent to finding the minimum weight perfect matching in the corresponding bipartite graph, in which the edge from i to j has weight M_{ij}.)

Now let us choose the entries of the matrix M independently at random according to the exponential distribution with mean 1. The problem that we pose ourselves is to compute the expected value of the minimum assignment. Using the (highly nonrigorous) replica method, Mézard and Parisi [37] predicted that

lim_{n→∞} E(min. assignment) = \frac{π^{2}}{6} .  (5.1)

(Instead of the exponential distribution, they do in fact consider the uniform distribution on [0, 1], but, modulo physical intuition, in the limit n → ∞ this is equivalent.) Several years later, Parisi [39] discovered that, apparently, there was a finite version of this conjecture.

Conjecture 4. If the entries of an n × n matrix M are chosen independently, each according to the exponential distribution with mean 1, then

E(min. assignment) = 1 + \frac{1}{4} + \frac{1}{9} + ⋯ + \frac{1}{n^{2}} .

Clearly, this is well in accordance with the prediction (5.1).

When one first sees the conjecture then one has the feeling that one should be able to resolve it during a weekend, say. However, one quickly realizes that the simplicity of the statement is deceiving. In particular, it is probably too special to be approached directly, so that one is quickly led to look for generalizations that may be easier to prove. One possible direction of generalization could be to extend the conjecture to rectangular matrices, m × n matrices M say. In that case, one has to also adapt the notion of assignment. In fact, we generalize the concept to the concept of a k-assignment of M, which is a selection of k elements of M out of which no two elements are in the same row or in the same column. For example, for the 3 × 5 matrix in Figure 6, the circled elements mark a 2-assignment, which is in fact also a minimum 2-assignment.

Coppersmith and Sorkin [23] came up with the following surprising generalization of Conjecture 4.

Conjecture 5. If the entries of an m × n matrix M are chosen independently, each according to the exponential distribution with mean 1, then

E(min. k-assignment) = ∑_{i+j<k} \frac{1}{(m − i)(n − j)}.

It is not immediately obvious, but it is not too difficult to show, that for m = n = k this implies Conjecture 4.

The reader may wonder why we did not consider another source of possible generalization: why not replace the exponential distribution with mean 1 by exponential distributions with other means? (That the distribution needs to be exponential seems to be instrumental if one wants to have exact results for the finite problem.) This leads us to the conjecture by Buck, Chan and Robbins [20].

Conjecture 6. If the entries of an m × n matrix M are chosen independently, the (i, j)-entry according to the exponential distribution with mean 1/u_{i}v_{j}, then

E(min. k-assignment) = _{∑_{X⊆\{1,...,n\}} ; Y ⊆\{1,...,n\}}\binom{m + n − 1 − |X| − |Y |}{k − 1 − |X| − |Y |}\frac{(−1)^{k−1−|X|−|Y |}}{uX̄vȲ} ,

where uX̄ = _{∑_{i=1}^{m} ; i∉X}u_{i}, and similarly for vȲ.

Again, it is not completely obvious but not too difficult to show that Conjecture 6 implies Conjecture 5, and thus Conjecture 4, see [20].

Now, a naïve way to try to prove this is to somehow apply induction. For example, let us suppose that M_{11} happens to be the smallest element in the first row. One can show that, conditioning on that event, the differences M_{12} − M_{11}, …, M_{1n} − M_{11} are again independent and exponentially distributed. Hence, one subtracts M_{11} from all the entries in the first row, thus creating a 0 in the place of the (1, 1)-entry. One could imagine to do something similar for other rows, or columns. In the end, one will realize that, for such an approach to be successful, it will be necessary to have a formula for matrices in which some entries are fixed to be 0. Such a formula was found, and proved, by Linusson and Wästlund [36], see the theorem below. (It generalizes a previous one from [35], which was already sufficient to prove Conjectures 4 and 5. We should remark that a proof of the prediction (5.1) was found earlier by Aldous [1], and that a proof of Conjectures 4 and 5 different from the one in [35] has been found by Nair, Prabhakar and Sharma [38].)

Here is the main theorem from [36].

Theorem 7. Let M be a (random) m × n matrix in which the entries in a certain (fixed) set Z are all 0, while an (i, j)-entry outside of Z is distributed exponentially with mean 1/u_{i}v_{j}. Then

E(min. k-assignment) = ∑_{(X,Y)∈J_{k}(M)} \frac{−μ((X, Y), ˆ1)}{uX̄vȲ}.

Clearly, I need to explain the notation which is used in the statement of the theorem. A subset λ of the rows and columns of M is called a cover if all entries of Z are in λ. A (k −1)-cover is one consisting of exactly k −1 rows and columns. A partial (k −1)-cover is a subset of a (k − 1)-cover. Let J_{k}(M) be the set of partial (k − 1)-covers, and let Ĵ_{k}(M) be the poset consisting of the elements of J_{k}(M) ordered by inclusion, together with an artificial maximal element ˆ1. The function μ(., ˆ1) in the theorem denotes the Möbius function on the poset Ĵ_{k}(M), i.e., the function on Ĵ_{k}(M) which is uniquely determined by ∑_{B⊇A} μ(B, ˆ1) = δ_{A,ˆ1}. (The reader may have wondered what a problem such as the random assignment problem, which is clearly a probabilistic problem, may have to do with algebraic combinatorics. Now, with the appearance of the Möbius function, the relation with algebraic combinatorics becomes transparent.)

The proof of the theorem is based on a clever induction, elements from the “Hungarian method” for finding the minimum weight perfect matching in a bipartite graph, König’s theorem on matchings and vertex coverings in bipartite graphs, and an urn model invented by Buck, Chan and Robbins in [20]. Again, it is not obvious that Theorem 7 would imply Conjectures 4–6, but this is shown in [36].

6. The Charney–Davis and the Neggers–Stanley conjectures

Here I report on progress made by Reiner and Welker (Marburg team), and by Brändén (pre-doc in the network) on two tantalizing conjectures in poset theory and the theory of simplicial complexes: the Neggers–Stanley Conjecture and the Charney– Davis Conjecture. I refer the reader to [13, 46, 47] for an introduction into the relevant theory at the interplay between combinatorics and commutative algebra, and for more background information.

I begin by explaining the first of the two conjectures. Let P be a partially ordered set (poset) on {1, 2, …, n}. Let L(P) denote its set of linear extensions, that is, the set of w = (w_{1}, w_{2}, …, w_{n}) ∈ S_{n} for which i <_{P} j implies w^{−1}(i) < w^{−1}(j). The P -Eulerian polynomial

W (P, t) = ∑_{w∈L(P)} t^{des(w)}

is the generating function for the linear extensions w ∈ L(P) counted according to the number of descents des(w), which is the number of all i, 1 ≤ i ≤ n − 1, such that w_{i} > w_{i+1}. This polynomial arose originally in the context of Stanley’s theory of P -partitions [44], but has since then appeared and found applications in many other situations.

The Neggers–Stanley conjecture says the following.

Conjecture 8. For any labelled poset P on {1, 2, …, n}, the polynomial W (P, t) has only real (non-positive) zeroes.

Neggers had made this conjecture for naturally labelled posets, that is, for posets with the property that i <_{P} j implies i < j, and Stanley extended the conjecture to arbitrarily labelled posets. (I refer the reader to the references in [11, 12] for more background and information on this conjecture.)

Next, I recall the Charney–Davis Conjecture, a discrete analog of the famous Hopf conjecture on closed Riemannian manifolds of non-positive sectional curvature. Given an abstract simplicial complex Δ triangulating a (d−1)-dimensional (homology) sphere, the face numbers f_{i} count the number of i-dimensional faces. These face numbers are usually collected in the f-vector (f_{−1}, f_{0}, f_{2}, …, f_{d−1}). The information about the face numbers can also be equivalently, but very often more conveniently, encoded by the h-vector (h_{0}, h_{1}, …, h_{d}), defined by

∑_{i=0}^{d} h_{i}t^{d−i} = ∑_{i=0}^{d} f_{i−1}(t − 1)^{d−i}.

We denote the polynomial ∑_{i=0}^{d} h_{i}t^{i} by h(Δ, t). The Charney–Davis Conjecture [21, Conjecture D] concerns the evaluation of h(Δ, t) at t = −1 in the case where d is even and Δ is a flag simplicial homology (d − 1)-sphere, “flag” meaning that the minimal subsets of vertices which do not span a simplex all have cardinality two.

Conjecture 9. When Δ is a flag simplicial homology (d − 1)-sphere and d is even, then

(−1)^{d/2}h(Δ, −1) ≥ 0.

In [40], Reiner and Welker establish a link between these seemingly unrelated conjectures. Let P be a graded poset, that is, a poset in which every maximal chain has the same number of elements, r say. They construct a flag simplicial polytopal sphere Δ_{eq}(P) of dimension |P | − r − 1 (called the equatorial sphere) such that

W (P, t) = h(Δ_{eq}(P), t).  (6.1)

(Space does not permit to reproduce this construction here.) Furthermore, by using the fact that Δ_{eq}(P) is the boundary of a simplicial convex polytope, which makes it possible to apply the g-Theorem [45] characterizing the number of faces of such polytopes, they prove that the sequence of coefficients of W (P, t) is (symmetric and) unimodal. (A sequence is unimodal if its coefficients are weakly increasing up to a certain point, and from that point on weakly decreasing.) Since one can show that polynomials with real non-positive zeroes have automatically unimodal coefficients, this statement is slightly weaker than Conjecture 8 for graded posets. As a consequence, the Neggers–Stanley Conjecture for P implies the Charney–Davis Conjecture for Δ_{eq}(P), because it is well-known that if p(t) = p_{d}t^{d} + ⋯ + p_{1}t + p_{0} is a polynomial in t with non-negative coefficients of even degree, and if p(t) is symmetric and has only real zeroes, then (−1)^{d/2}p(−1) ≥ 0. The paper [40] does in fact put forward evidence for the thesis that both of the conjectures should be fruitfully viewed within the context of Koszul algebras. It is worthwhile to point out that this work inspired Athanasiadis [3] to find a powerful general theorem which implies the above result by Reiner and Welker, and proves at the same Stanley’s conjecture on the unimodality of the h-vector of the Birkhoff polytope of magic squares.

In [11], Brändén gives a different proof (avoiding the powerful g-Theorem) of symmetry and unimodality of the coefficients of W (P, t), in the generalized context of, what he calls, sign-graded posets P. Moreover, he is able to prove that W (P, −1) has always the “right” sign, so that, via (6.1), the Charney–Davis Conjecture holds for all the flag simplicial polytopal spheres Δ_{eq}(P).

On the slightly negative side, Brändén constructs counter-examples to the Neggers– Stanley Conjecture in [12]. However, all his examples are not naturally labelled posets, so that it is still possible that Neggers’ original conjecture is true. There may well be also other important families of posets for which the Neggers–Stanley conjecture is

Figure 7. A map, an Ising configuration, and a hard particle configuration

still true. (In fact, this is known for some already, see [11] for references.) Also the Charney–Davis Conjecture may still be true in general.

7. Map enumeration

The subject of this final section is the recent work by Bousquet–Mélou (Bordeaux team) and Schaeffer (Marne-la-Vallée team) on map enumeration.

A map is an embedding of a connected graph on a surface without crossing edges. The connected components of the complement of the graph in the surface are called faces of the map. For our purposes, the surface will always be the plane. For such a planar map, one usually marks one edge on the outer face and orients it so that the outer face is to the right of the edge. This marked edge is called the root edge of the map. Figure 7.a shows a rooted planar map. The root edge is indicated by the arrow.

In the Ising model on maps, one colours the vertices of the map in two colours, black and white, say; see Figure 7.b. (In the figure, “bicoloured” edges, that is, edges between vertices of different colour are dotted.) The task is then to compute the partition function (generating function, in combinatorial terms)

∑_{m∈C} 2-colourings of mX^{#white vertices of m} Y^{#black vertices of m} u^{#bicoloured edges},

for a given class C of maps.

In the hard particle model on maps, we are allowed to place “hard” particles on the vertices, but two hard particles can never be placed on neighbouring vertices. See Figure 7.c for an example. Here, the task is to compute the partition function (generating function)

∑_{m∈C} particle configurationsX^{#empty vertices of m} Y^{#particles},

for a given class C of maps.

Before I become more specific, let me recall some (very selective) history: Map enumeration begins with the fundamental work of Tutte (see e.g. [18, 48, 49]). Among other things, using the so-called quadratic method and Lagrange inversion, he derived miraculous closed form expressions for the number of maps in several classes of maps. The long-standing question of giving a (combinatorial) explanation of why these closed form formulas arise, was answered by Schaeffer [42, 43], by constructing new bijections between maps and trees. On the physics side, the idea of putting models on maps originates from two-dimensional quantum gravity (see [5, 17]). In many cases, the physicists found (most of the time using matrix integrals; see [25] for a recent survey) nice algebraic partition functions. Again, the question arises why these nice algebraic functions arise. Bousquet-Mélou and Schaeffer [8] give the answer again in terms of bijections between maps and trees. (This paper extends largely a previous one [10] by Bouttier, Di Francesco and Guitter, which is as well based on “Schaeffer-like” bijections.)

Bousquet-Mélou and Schaeffer consider a very fine partition function (generating function) for bipartite maps (these are maps in which the vertices are coloured black or white, and each edge connects a black and a white vertex), namely

∑_{m a bipartite map} ∏_{i≥1} x_{i}^{#white vertices of degree i in m} ∏_{i≥1} y_{i}^{#black vertices of degree i in m}.

The main theorem that they prove is the following.

Theorem 10. The above degree generating function for bipartite maps rooted at a black vertex of degree 2 (i.e., the root edge is directed from a black vertex to a white vertex, and the black vertex has degree 2) is equal to

y_{2}((W_{0} − B_{2})^{2} + W_{1} − B_{3} − B_{2}^{2}),  (7.1)

where the W_{i} ≡ W_{i}(x_{1}, …, y_{1}, …) and B_{i} ≡ B_{i}(x_{1}, …, y_{1}, …) are degree generating functions for certain families of trees. The latter can be calculated from the system of equations

W_{i} = [z^{i}] ∑_{k≥0} x_{k+1}(z + B(z))^{k},

and

B_{i} = [z^{i}] ∑_{k≥0} y_{k+1} (\frac{1}{z} + W (z))^{k} ,

where W (z) := ∑_{i≥0} W_{i}z^{i} and B(z) := ∑_{i≤1} B_{i}z^{i}, and where [z^{i}]S(z) denotes the coefficient of z^{i} in the series S(z).

The point is that the above definition of the auxiliary generating functions W_{i} and B_{i} implies that, once one poses certain additional restrictions (for example: restrict oneself to maps in which the vertices have bounded degree), one finds easily polynomial equations for the W_{i}’s and B_{i}’s. (As a consequence, the generating function in (7.1) is algebraic in these cases, which gives the desired explanation for the phenomena observed by physicists mentioned earlier. Not only that, all the terms in (7.1) have a precise combinatorial meaning as generating functions of trees.) Furthermore, suitable specializations, respectively limits, produce the afore-mentioned Ising and hard particle generating functions. To illustrate the power of the theorem, here are two corollaries obtained in this manner. (The first one was originally obtained, in an equivalent form, by Bouttier, Di Francesco and Guitter [7], while the second was originally obtained, again in equivalent form, by Boulatov and Kazakov [9].)

Corollary 11. The hard particle generating function for tetravalent maps (these are maps in which all the vertices have degree 4; see Figure 7.a for an example of such a

Figure 8. Cutting the root edge

map) rooted at an edge whose ends are vacant (i.e., the vertices which the root edge connects are not occupied by a particle) is

xP^{3} + \frac{xP^{2}(3 − 2P)}{1 − 9xyP^{2}} − \frac{27x^{3}yP^{6}}{(1 − 9xyP^{2})^{3}}

where P ≡ P (x, y) is the power series defined by

P = 1 + 3xyP^{3} + \frac{3xP^{2}}{(1 − 9xyP^{2})^{2}} .

Corollary 12. The Ising generating function for bicoloured tetravalent maps rooted at a white vertex is

I(X, Y, u) = \frac{1}{9}(135x^{2}y^{2}P^{6} + 72xy^{2}P^{5} − 3y(15x + 8y − 3v^{2}y + 36xy)P^{4}

− y(32 + 3v^{2} − 36x − 36y)P^{3} − (3 + 2v^{2} − 72y)P^{2} + 12(1 − 3y)P − 9)

+ \frac{(1 − P − yP^{2})(1 + 3yP)(12 − 8P + 3v^{2}P)}{9(1 + 3xP)},

where P ≡ P (x, y, v) is defined by

P = 1 + 3xyP^{3} + v^{2} \frac{P (1 + 3xP)(1 + 3yP)}{(1 − 9xyP^{2})^{2}},

and where x = X(u − \frac{1}{u})^{2}, y = Y (u − \frac{1}{u})^{2} and v = \frac{1}{u}.

The proof of Theorem 10 relies, first of all, on a (trivial) decomposition of maps which results by cutting the root edge: either the map gets disconnected when we cut the root edge (see the left half of Figure 8), in which case we end up with two maps, each with a pending (half-)edge, or the map stays connected (see the right half of Figure 8), in which case we end up with one map which contains two pending (half-)edges.

The heart of the proof is then a bijection between maps with one or two pending half-edges and certain trees, called blossom trees. These are rooted trees with white and black vertices, in which neighbouring vertices must have different colour, in which black vertices may have buds (indicated by arrows) and white vertices may have leafs (indicated by half-edges). See Figure 9 for an example.

Given a blossom tree, one can construct a map by the following closure procedure. Starting from the root, we go around the tree, and, whenever we encounter a bud

Figure 9. A blossom tree

Figure 10. The closure of a blossom tree

immediately followed by a leaf, we connect the two by an edge. See Figure 10 for an example.

It can be shown that, under certain additional (technical) conditions, this defines a bijection. If one puts the pieces together appropriately, one arrives finally at the assertion of Theorem 10.

References

[1] D. Aldous, The ζ(2) limit in the random assignment problem, Random Structures Algorithms 18 (2001), 381–418.

[2] S. E. Alm and G. B. Sorkin, Exact expectations and distributions in the random assignment problem, Combin. Probab. Comput. 11 (2002), 217–248.

[3] C. Athanasiadis, Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, preprint, 2003; math.CO/0312031.

[4] A. Beilinson and J. Bernstein, Localisation de g-modules, C. R. Acad. Sci. Paris 292 (1981), 15–18.

[5] D. Bessis, C. Itzykson and J. B. Zuber, Quantum field theory techniques in graphical enumeration, Adv. Appl. Math. 1(2) (1980), 109–157.

[6] S. Billey and V. Lakshmibai, Singular loci of Schubert varieties, Progress in Math. 182, Birkhäuser, Boston, MA, 2000.

[7] D. V. Boulatov and V. A. Kazakov, The Ising model on a random planar lattice: the structure of the phase transition and the exact critical exponents, Phys. Lett. B 186(3-4) (1987), 379–384.

[8] M. Bousquet-Mélou and Schaeffer, The degree distribution in bipartite planar maps: applications to the Ising model, preprint, 2003; math.CO/0211070.

[9] J. Bouttier, P. Di Francesco and E. Guitter, Critical and tricritical hard objects on bicolourable random lattices: exact solutions, J. Phys. A 35(17) (2002), 3821–3854.

[10] J. Bouttier, P. Di Francesco and E. Guitter, Census of planar maps: from the one-matrix model solution to a combinatorial proof, Nucl. Phys. B645 (2002), 477-499.

[11] P. Brändén, Sign-graded posets, unimodality of W-polynomials and the Charney–Davis Conjecture,

preprint, 2004; math.CO/0406019.

[12] P. Brändén, Counterexamples to the Neggers–Stanley conjecture, preprint, 2004;

math.CO/0408312.

[13] F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Contemp. Math. 178 (1994), 71–89.

[14] F. Brenti, Kazhdan-Lusztig polynomials: History, Problems, and Combinatorial Invariance, Séminaire Lotharingien Combin. 46 (2003), Article B46c, 30 pp.

[15] F. Brenti, The intersection cohomology of Schubert varieties is a combinatorial invariant, Europ. J. Combin. 25 (2004), 1151–1167.

[16] F. Brenti, F. Caselli and M. Marietti, Special matchings and Kazhdan-Lusztig polynomials for doubly laced Coxeter systems, preprint, 2003.

[17] E. Brézin, C. Itzykson, G. Parisi and J. B. Zuber, Planar diagrams, Comm. Math. Phys. 59(1) (1978), 35–51.

[18] W. G. Brown and W. T. Tutte, On the enumeration of rooted non-separable planar maps, Canad. J. Math. 16 (1964), 572–577.

[19] J.-L. Brylinski and M. Kashiwara, Kazhdan-Lusztig conjecture and holonomic system, Invent. Math. 64 (1981), 387–410.

[20] M. W. Buck, C. S. Chan and D. P. Robbins, On the expected value of the minimum assignment, Random Structures Algorithms 21 (2002), 33–58.

[21] R. Charney and M. Davis, Euler characteristic of a nonpositively curved, piece-wise Euclidean manifold, Pacific J. Math. 171 (1995), 117–137.

[22] F. du Cloux, Rigidity of Schubert closures and invariance of Kazhdan-Lusztig polynomials, Adv. in Math. 180 (2003), 146–175.

[23] D. Coppersmith and G. B. Sorkin, Constructive bounds and exact expectations for the random assignment problem, Random Structures Algorithms 15 (1999), 133–144.

[24] E. Delanoy, Invariance combinatoire des polynômes de Kazhdan–Lusztig sur les intervalles partant de l’origine, preprint, 2003; math.CO/0312237.

[25] P. Di Francesco, 2D quantum gravity, matrix models and graph combinatorics, preprint, 2004;

math-ph/0406013.

[26] M. J. Dyer, On the ”Bruhat graph” of a Coxeter system, Compositio Math. 78 (1991), 185–191.

[27] I. Frenkel, M. Khovanov and A. Kirillov, Kazhdan-Lusztig polynomials and canonical basis, Transform. Groups 3 (1998), 321–336.

[28] W. Fulton, Young tableaux, Cambridge University Press, Cambridge, 1997.

[29] W. Fulton and J. Harris, Representation Theory, Springer–Verlag, New York, 1991.

[30] M. Haiman, Hecke algebra characters and immanant conjectures, J. Amer. Math. Soc. 6 (1993), 569–595.

[31] J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, 1990.

[32] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.

[33] D. Kazhdan and G. Lusztig, Schubert varieties and Poincaré duality, Geometry of the Laplace operator, Proc. Sympos. Pure Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185–203.

[34] V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in S_{l(n)/B}, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), 45-52.

[35] S. Linusson and J. Wästlund, A proof of Parisi’s conjecture on the random assignment problem, Probab. Theory Related Fields 128 (2004), 419–440.

[36] S. Linusson and J. Wästlund, A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem, preprint; math.CO/0307357.

[37] M. Mézard and G. Parisi, Replicas and optimization, J. Phys. Lett. 46 (1985), 771–778.

[38] C. Nair, B. Prabhakar and M. Sharma, A proof of the conjecture due to Parisi for the finite random assignment problem, preprint, 2003; available at http://www.stanford.edu/~balaji/rap.html.

[39] G. Parisi, A conjecture on random bipartite matching, manuscript, 1998; cond-mat/9801176.

[40] V. Reiner and V. Welker, On the Charney-Davis and Neggers-Stanley conjectures, preprint, 2002;

    available from http://www.mathematik.uni-marburg.de/~welker.

[41] B. E. Sagan, The symmetric group, 2nd edition, Springer–Verlag, New York, 2001.

[42] G. Schaeffer, Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees, Electron. J. Combin. 4(1) (1997), #R20, 14 pp.

[43] G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires, Ph.D. thesis, Université Bordeaux 1, France, 1998.

[44] R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. No. 119, Amer. Math. Soc., Providence, R. I., 1972.

[45] R. P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), 236–238.

[46] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989), 500–534.

[47] R. P. Stanley, Combinatorics and commutative algebra, 2nd edition, Birkhäuser, Basel, 1996.

[48] W. T. Tutte, A census of planar maps, Canad. J. Math. 15 (1963), 249–271.

[49] W. T. Tutte, On the enumeration of planar maps, Bull. Amer. Math. Soc. 74 (1968), 64–74.

[50] D. Uglov, Canonical bases of higher level q-deformed Fock spaces and Kazhdan-Lusztig polynomials, Physical Combinatorics, Progress in Math., 191, Birkhäuser, Boston, MA, 2000, 249–299.

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France