\documentclass[12pt,reqno]{amsart}

\usepackage{epsfig}


\textwidth15.6cm
\textheight22.8cm
\hoffset-1truecm
\voffset-.5truecm

\newtheorem{Theorem}{Theorem}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Lemma}[Theorem]{Lemma} 
\newtheorem{Proposition}[Theorem]{Proposition} 
\newtheorem{Conjecture}[Theorem]{Conjecture}

\theoremstyle{remark}

\newtheorem*{Remark}{Remark}
\newtheorem*{Definition}{Definition}

\numberwithin{equation}{section}


\font\Bf=cmbx12
\font\Rm=cmr12
\def\LL{\leavevmode\setbox0=\hbox{L}\hbox to\wd0{\hss\char'40L}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\de{\delta}
\def\ep{\varepsilon}
\def\ze{\zeta}
\def\et{\eta}
\def\th{\theta}
\def\vt{\vartheta}
\def\io{\iota}
\def\ka{\kappa}
\def\la{\lambda}
\def\rh{\rho}
\def\si{\sigma}
\def\ta{\tau}
\def\ph{\varphi}
\def\ch{\chi}
\def\ps{\psi}
\def\om{\omega}
\def\Ga{\Gamma}
\def\De{\Delta}
\def\Th{\Theta}
\def\La{\Lambda}
\def\Si{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\Om{\Omega}
\def\x{\times}
\def\crf{}            %used for crossreferencing, Tex should ignore.
\def\rf{}             %used for refencing (section-numbers)
\def\rfnew{}          %used for new-section numbers
\def\P{{\Bbb P}}
\def\R{{\Bbb R}}
\def\X{{\mathcal X}}
\def\C{{\Bbb C}}
\def\Mf{{\mathcal Mf}}
\def\FM{{\mathcal F\mathcal M}}
\def\F{{\mathcal F}}
\def\G{{\mathcal G}}
\def\V{{\mathcal V}}
\def\T{{\mathcal T}}
\def\A{{\mathcal A}}
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\Q{{\Bbb Q}}
\def\ddt{\left.\tfrac \partial{\partial t}\right\vert_0}
\def\dd#1{\tfrac \partial{\partial #1}}
\def\today{\ifcase\month\or
 January\or February\or March\or April\or May\or June\or
 July\or August\or September\or October\or November\or December\fi
 \space\number\day, \number\year}
\def\nmb#1#2{#2} %zum Nummerieren
\def\totoc{} % f\"ur Inhaltsverzeichnung
%\def\dfrac#1#2{{\displaystyle{#1\over#2}}}
%\def\tfrac#1#2{{\textstyle{#1\over#2}}}
\def\iprod#1#2{\langle#1,#2\rangle}
\def\pder#1#2{\frac{\partial #1}{\partial #2}}
\def\iint{\int\!\!\int}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\supp{\operatorname{supp}}
\def\Df{\operatorname{Df}}
\def\dom{\operatorname{dom}}
\def\Ker{\operatorname{Ker}}
\def\Tr{\operatorname{Tr}}
\def\Res{\operatorname{Res}}
\def\Aut{\operatorname{Aut}}
\def\kgV{\operatorname{kgV}}
\def\ggT{\operatorname{ggT}}
\def\diam{\operatorname{diam}}
\def\Im{\operatorname{Im}}
\def\Re{\operatorname{\frak R\frak e}}
\def\ord{\operatorname{ord}}
\def\rang{\operatorname{rang}}
\def\rng{\operatorname{rng}}
\def\grd{\operatorname{grd}}
\def\inv{\operatorname{inv}}
\def\maj{\operatorname{maj}}
\def\des{\operatorname{des}}
\def\varmaj{\operatorname{\overline{maj}}}
\def\vardes{\operatorname{\overline{des}}}
\def\pvarmaj{\operatorname{\overline{maj}'}}
\def\pmaj{\operatorname{maj'}}
\def\ln{\operatorname{ln}}
\def\der{\operatorname{der}}
\def\Hom{\operatorname{Hom}}
\def\tr{\operatorname{tr}}
\def\Span{\operatorname{Span}}
\def\grad{\operatorname{grad}}
\def\div{\operatorname{div}}
\def\rot{\operatorname{rot}}
\def\Sp{\operatorname{Sp}}
\def\sgn{\operatorname{sgn}}
\def\liml{\lim\limits}
\def\supl{\sup\limits}
\def\bigcupl{\bigcup\limits}
\def\bigcapl{\bigcap\limits}
\def\limsupl{\limsup\limits}
\def\liminfl{\liminf\limits}
\def\intl{\int\limits}
\def\suml{\sum\limits}
\def\maxl{\max\limits}
\def\minl{\min\limits}
\def\prodl{\prod\limits}
\def\tg{\operatorname{tan}}
\def\ctg{\operatorname{cot}}
\def\arctg{\operatorname{arctan}}
\def\arccot{\operatorname{arccot}}
\def\arcctg{\operatorname{arccot}}
\def\tgh{\operatorname{tanh}}
\def\ctgh{\operatorname{coth}}
\def\arcsinh{\operatorname{arcsinh}}
\def\arccosh{\operatorname{arccosh}}
\def\arctgh{\operatorname{arctanh}}
\def\arcctgh{\operatorname{arccoth}}
\def\3{\ss}
\def\sp{\operatorname{\text {\it sp}}}
\def\so{\operatorname{\text {\it so}}}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\cl#1{\left\lceil#1\right\rceil}
\def\coef#1{\left\langle#1\right\rangle}


\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc C.~Krattenthaler$^\dagger$}
\vskip18pt
\centerline{Institut Girard Desargues,
Universit\'e Claude Bernard Lyon-I}
\centerline{21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France}
\centerline{E-mail: \tt kratt@euler.univ-lyon1.fr}
\centerline{WWW: \footnotesize\tt http://igd.univ-lyon1.fr/\~{}kratt}
}


\title{The Research Training Network ``Algebraic Combinatorics in Europe"}
\author[C. Krattenthaler]{\box\Adr}
\address{Institut Girard Desargues,
Universit\'e Claude Bernard Lyon-I,
21, avenue Claude Bernard,
F-69622 Villeurbanne Cedex, France}
\thanks{$^\dagger$ Research partially supported 
by EC's IHRP Programme, grant HPRN-CT-2001-00272, 
``Algebraic Combinatorics in Europe"}

%\subjclass[2000]{Primary 05A16;
% Secondary 05E05 05E15 60G50 82B23 82B41}

%\keywords{random walks, reflection principle,
%alcoves of affine Weyl groups, vicious walkers,
%nonintersecting lattice paths, cylindric partitions,
%Schur functions, symplectic characters, 
%orthogonal characters}

\begin{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\"oping,
Lyon, Marburg, Marne-la-Vall\'ee, Roma, and Wien:
$\bullet$ 
the proof of the combinatorial invariance conjecture for Kazhdan--Lusztig
   polynomials in an important special case;
$\bullet$  the proof of the conjectures on the random assignment problem;
$\bullet$  important progress on the Neggers--Stanley Conjecture on posets 
and the Charney-Davis conjecture on (certain)
   simplicial complexes;
$\bullet$  new bijections between maps and trees with interesting applications
   to the Ising and the hard particle model on maps.
\end{abstract}
\maketitle

\section{Brief introduction to ACE} \label{sec:1}

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

\begin{itemize} 
\item the {\it Universit\'e Bordeaux 1} (Scientist-in-Charge: Mireille
Bousquet-M\'elou);
\item the {\it Hebrew University of Jerusalem}, the {\it Weizmann
Institute, Rehovot} and the {\it Bar Ilan University, Ramat Gan} 
(Scientist-in-Charge: Ehud
Friedgut);
\item {\it Link\"opings Universitet, KTH Stockholm
and Chalmers Tekniska H\"ogskola}\break
(Scientist-in-Charge: Svante Linusson);
\item the {\it Universit\'e Claude Bernard Lyon 1 - CNRS Rh\^one--Alpes} 
(Scientist-in-\break Charge: Christian
Krattenthaler); before,
until August 31, 2003: {\it Universit\'e Louis Pasteur,
Strasbourg} (Scientist-in-Charge: Dominique Foata);
\item the {\it Universit\'e de Marne-la-Vall\'ee} (Scientists-in-Charge: Jacques
D\'esarm\'enien and Jean-Yves Thibon);
\item the {\it Philipps--Universit\"at Marburg} (Scientist-in-Charge: Volkmar
Welker);
\item the {\it Universit\`a di Roma ``Tor Vergata"} (Scientist-in-Charge:
Francesco Brenti);
\item the {\it Universit\"at Wien} (Scientist-in-Charge: Markus Fulmek).
\end{itemize}

The members of the {\it Scientific Committee} of the network are
Anders Bj\"orner, 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
$$\text{\tt http://igd.univ-lyon1.fr/\~{}kratt/ace}$$
for the various activities (the series of meetings {\it S\'eminaire
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~\ref{sec:themes}, I shall give a list of themes and objects
that the teams of the network are interested in. Finally, in
Sections~\ref{sec:KL}--\ref{sec:maps}, I present some of the advances
that have been made by members of the network which I consider
important.

\section{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, {\it representation theory of the
symmetric group} (cf.\ \cite{FultAC,FuHaAA,SagaAQ}). This is an
algebraic subject, the study of which leads {\it necessarily} 
to combinatorial
objects like {\it partitions} (which label the irreducible
representations), {\it standard Young tableaux} (for constructing
bases of the irreducible representations), and to combinatorial algorithms
like the {\it Robinson--Schensted correspondence} and 
{\it Sch\"utzenberger's jeu de taquin}, which play an essential
role in deeper studies of the subject. Let us content ourselves with

\medskip
{\leftskip1cm\rightskip1cm
\noindent
\it{\bf 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,

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

\section{The research themes of ACE}
\label{sec:themes}
The ``definition" given in the previous section is clearly still rather
wide. More specifically, the research of the network features three
main directions: {\it Enumerative Combinatorics}
(with permutations, words, plane partitions, alternating sign matrices, fully
packed loop configurations, maps, trees, paths as objects of study), 
{\it 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 {\it 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.

\section{Combinatorial invariance of Kazhdan--Lusztig polynomials} 
\label{sec:KL}

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 \cite[Ch.~7]{HumpAC} and
\cite[Ch.~6]{BL}. I also point
out the survey article \cite{BretAZ}.

The {\it Kazhdan--Lusztig polynomials} are polynomials $P_{u,v}(q)$ in
$q$, which are indexed by elements $u,v$ of a {\it 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,\dots,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 $\si=\si_1\si_2\dots\si_n$, meaning the permutation
$$\si=\begin{pmatrix}
1&2&\dots&n\\\si_1&\si_2&\dots&\si_n\end{pmatrix}.$$
The {\it length\/} of a permutation $\si$, denoted by $\ell(\si)$, is the
number of {\it inversions} of $\si$, an inversion being a pair $(i,j)$
with $i<j$ but $\si(i)>\si(j)$. For example, we have $\ell(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 {\it Bruhat order} on $S_n$, which I have to explain next. Let
$u,v\in S_n$. Write $u\to 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\circ (i,j)=v\quad \text{and}\quad \ell(u)<\ell(v).$$
For example, we have $2143\to 3142$. Figure~\ref{fig1} shows the {\it Bruhat
graph\/} for $S_3$, which is the graph containing all the relations
$\to$ for $S_3$.

\begin{figure}[h]
\begin{picture}(80,80)(-30,-30)
\put(0,0){\vector(2,1){25}}
\put(0,0){\vector(-2,1){25}}
\put(0,0){\line(2,-1){25}}
\put(0,0){\line(-2,-1){25}}
\put(0,-25){\vector(0,10){50}}
\put(25,20){\vector(-3,2){15}}
\put(-25,20){\vector(3,2){15}}
\put(10,-30){\vector(3,2){15}}
\put(-10,-30){\vector(-3,2){15}}
\put(35,-8){\vector(0,1){18}}
\put(-35,-8){\vector(0,1){18}}
\put(0,-35){\makebox(0,0){123}}
\put(0,35){\makebox(0,0){321}}
\put(-35,-15){\makebox(0,0){213}}
\put(-35,15){\makebox(0,0){312}}
\put(35,-15){\makebox(0,0){132}}
\put(35,15){\makebox(0,0){231}}
\end{picture}
\caption{\protect\small The Bruhat graph of $S_{3}$}
\label{fig1}
\end{figure}

The Bruhat order then is the partial order on $S_n$ which is the transitive
closure of the relation $\to$, that is,
$$\begin{matrix} u\le v\\\vphantom{h}\end{matrix} \qquad 
\begin{matrix} \text{if $u=v$  or else there exist
$w_1,w_2,\dots,w_k$}\hfill\\
\text{such that $u\to w_1\to\dots\to w_k\to v$.}\hfill
\end{matrix}$$
Figure~\ref{fig2} shows the Hasse diagram of the Bruhat order on $S_3$
(which encodes the partial order $\le$ in the way that $u\le v$ if
and only if $u$ is lower than $v$ and there is an
upward path from $u$ to $v$ in the diagram).

\begin{figure}[h]
\begin{picture}(80,100)
\put(40,15){\line(1,1){20}}
\put(40,15){\line(-1,1){20}}
\put(20,35){\line(0,1){30}}
\put(20,65){\line(1,1){20}}
\put(40,85){\line(1,-1){20}}
\put(60,65){\line(0,-1){30}}
\put(20,35){\line(4,3){40}}
\put(20,65){\line(4,-3){40}}
\put(40,15){\circle*{2}}
\put(20,35){\circle*{2}}
\put(20,65){\circle*{2}}
\put(40,85){\circle*{2}}
\put(60,65){\circle*{2}}
\put(60,35){\circle*{2}}
\put(40,5){\makebox(0,0){$123$}}
\put(40,95){\makebox(0,0){$321$}}
\put(78,35){\makebox(0,0){$213$}}
\put(78,65){\makebox(0,0){$312$}}
\put(2,35){\makebox(0,0){$132$}}
\put(2,65){\makebox(0,0){$231$}}
\end{picture}
\caption{\protect\small The Bruhat order of $S_{3}$}
\label{fig2}
\end{figure}

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 {\it $R$-polynomials}. These are also polynomials in $q$
indexed by pairs of permutations. The definition of the
$R$-polynomials $R_{u,v}(q)$, $u,v\in S_n$, is recursive:

\begin{itemize} 
\item $R_{u,v}(q)=0$ if $u\not\le v$;
\item $R_{u,v}(q)=1$ if $u=v$;
\item for any adjacent transposition $s=(i,i+1)$, we have
$$R_{u,v}(q)=\begin{cases} R_{us,vs}(q)&\text{if }\ell(us)<\ell(u),\\
qR_{us,vs}(q)+(q-1)R_{u,vs}(q)&\text{if }\ell(us)>\ell(u).\end{cases}$$
\end{itemize}

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 \cite{K-L} (see also
\cite[Sec.~7.5]{HumpAC}). 

The Kazhdan--Lusztig polynomials $P_{u,v}(q)$, $u,v\in S_n$, are then
defined by 

\begin{itemize} 
\item $P_{u,v}(q)=0$ if $u\not\le v$;
\item $P_{u,v}(q)=1$ if $u=v$;
\item $\deg\big(P_{u,v}(q)\big)<\frac {1}
{2}\big(\ell(v)-\ell(u)\big)$ if $u<v$;
\item $q^{\ell(v)-\ell(u)}P_{u,v}\left(1/q\right)=
\sum _{u\le a\le v} ^{}R_{u,a}(q)\,P_{a,v}(q)$ if $u\le v$,
\end{itemize}
which involves the $R$-polynomials in the last rule.
Again, one can show that this is a coherent definition (see \cite{K-L}
or \cite[Sec.~7.10 and 7.11]{HumpAC}).

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.)

{\it However}: Kazhdan--Lusztig polynomials for a Coxeter group $W$ 
are instrumental in the
construction of certain important representations of the {\it Hecke algebra}
associated to $W$. This is, in fact, where these polynomials arose for
the first time \cite{K-L}. (In that context, the artificially looking
definition of the Kazhdan--Lusztig polynomials becomes natural.) 
Furthermore, Kazhdan and Lusztig have shown
in \cite{KL2} that, for {\it Weyl groups} $W$, the coefficients of
$P_{u,v}(q)$ are dimensions of local intersection homology of the
{\it 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., \cite{BB}, \cite{BK}), the algebraic
geometry and topology of Schubert varieties 
(see, e.g., \cite{KL2}, \cite{La-Se},
\cite{BL}), canonical bases (\cite{FKK}, \cite{Ug}), 
and immanant inequalities (\cite{Ha}). 

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 \cite{Dye1} made the
following surprising {\it invariance conjecture}.

\begin{Conjecture} \label{conj1}
$P_{u,v}(q)$ depends only on the combinatorial structure of the
interval $[u,v]:=\{x:u\le x\le v\}$; that is, given two Coxeter groups
$W$ and $W'$, if $u,v\in W$ and
$u',v'\in W'$, and if $[u,v]\cong[u',v']$ as partially ordered sets
(posets), then
$$P_{u,v}(q)=P_{u',v'}(q).$$
\end{Conjecture}

For example, if $W=W'=S_4$, then the intervals $[1234,3142]$ and
$[1234,4123]$ are isomorphic as posets, as is shown in
Figure~\ref{fig:3}, and indeed one can verify that $P_{1234,3142}(q)=
P_{1234,4123}(q)=1$.

\begin{figure}[h]
\begin{picture}(140,140)(-80,0)
\put(-70,0){\line(2,1){50}}
\put(-90,0){\line(-2,1){50}}
\put(-80,0){\line(0,1){25}}
\put(-70,35){\line(2,1){50}}
\put(-90,35){\line(-2,1){50}}
\put(-20,35){\line(0,1){25}}
\put(-140,35){\line(0,1){25}}
\put(-130,35){\line(2,1){50}}
\put(-30,35){\line(-2,1){50}}
\put(-140,70){\line(2,1){50}}
\put(-20,70){\line(-2,1){50}}
\put(-80,70){\line(0,1){25}}

\put(-80,-5){\makebox(0,0){1234}}
\put(-20,30){\makebox(0,0){2134}}
\put(-80,30){\makebox(0,0){1243}}
\put(-140,30){\makebox(0,0){1324}}

\put(-20,65){\makebox(0,0){2143}}
\put(-80,65){\makebox(0,0){3124}}
\put(-140,65){\makebox(0,0){1342}}

\put(-80,100){\makebox(0,0){3142}}

%
\put(90,0){\line(2,1){50}}
\put(70,0){\line(-2,1){50}}
\put(80,0){\line(0,1){25}}
\put(90,35){\line(2,1){50}}
\put(70,35){\line(-2,1){50}}
\put(140,35){\line(0,1){25}}
\put(20,35){\line(0,1){25}}
\put(30,35){\line(2,1){50}}
\put(130,35){\line(-2,1){50}}
\put(20,70){\line(2,1){50}}
\put(140,70){\line(-2,1){50}}
\put(80,70){\line(0,1){25}}

\put(80,-5){\makebox(0,0){1234}}
\put(140,30){\makebox(0,0){2134}}
\put(80,30){\makebox(0,0){1324}}
\put(20,30){\makebox(0,0){1243}}

\put(140,65){\makebox(0,0){3124}}
\put(80,65){\makebox(0,0){2143}}
\put(20,65){\makebox(0,0){1423}}

\put(80,100){\makebox(0,0){4123}}

\end{picture}
\caption{\protect\small The intervals  $[1234,3142]$ and
$[1234,4123]$}
\label{fig:3}
\end{figure}

Conjecture~\ref{conj1} has been shown by Brenti, Caselli and Marietti
\cite{BrCMAA} 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.

\begin{Theorem} \label{thm1}
For any Coxeter group, the Kazhdan--Lusztig polynomial $P_{e,v}(q)$
depends only on the poset structure of $[e,v]$.
\end{Theorem}

\begin{Remark} For the case of $W=W'=S_n$, this was proved by Brenti
\cite{BretAY}. Independently, du Cloux \cite{Cloux} showed this for
finite and affine Coxeter groups. Furthermore, Delanoy \cite{Dela}
proved it for simply-laced Coxeter groups.
\end{Remark}

The proof of Theorem~\ref{thm1} begins with the observation that it
suffices to show the claim for the $R$-polynomials, i.e., to show that
if $x,y\in [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 {\it
special matching} introduced in \cite{BretAY}. To motivate this idea,
let us recall that, given $s=(i,i+1)$ such that $\ell(vs)<\ell(v)$,
the map
\begin{equation} \label{eq:3} 
x\mapsto xs
\end{equation}
defines a matching of the elements of $[e,v]$ with the property:
\begin{equation} \label{eq:1} 
\text{if }x\lhd y\text{ and }xs\ne y,\text{ then }xs\le ys.
\end{equation}
(Here, $x\lhd 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 fixed-point free involution, i.e., as a function $M$
without fixed points such that $M(M(x))=x$ for all $x$.

\begin{Definition} \label{def1}
A matching $M$ is called {\em special} if for all $x$ and $y$ we have:
\begin{equation} \label{eq:2} 
\text{if }x\lhd y\text{ and }M(x)\ne y,\text{ then }M(x)\le M(y).
\end{equation}
\end{Definition}

The reader should note the analogy between \eqref{eq:1} and
\eqref{eq:2}. In particular, the map \eqref{eq:3} is a special
matching. 

\begin{figure}[h]
\begin{picture}(250,160)(-120,0)
\put(0,0){\line(-2,1){60}}
\put(0,0){\line(0,1){150}}
\put(0,0){\line(2,1){120}}
\put(-60,30){\line(6,1){180}}
\put(-60,30){\line(4,1){120}}
\put(-60,30){\line(2,1){120}}
\put(0,30){\line(-4,1){120}}
\put(0,30){\line(-2,1){60}}
\put(0,30){\line(2,1){60}}
\put(60,30){\line(-6,1){180}}
\put(60,30){\line(-4,1){120}}
\put(-120,60){\line(0,1){30}}
\put(-120,60){\line(2,1){120}}
\put(-120,60){\line(1,0){30}}
\put(-90,60){\line(6,1){180}}
\put(90,90){\line(1,0){30}}
\put(0,60){\line(2,1){60}}
\put(0,60){\line(4,1){120}}
\put(60,60){\line(-4,1){120}}
\put(60,60){\line(0,1){60}}
\put(120,60){\line(-6,1){180}}
\put(120,60){\line(-4,1){120}}
\put(120,60){\line(0,1){30}}
\put(-120,90){\line(2,1){120}}
\put(-120,90){\line(4,1){120}}
\put(-60,90){\line(4,1){120}}
\put(60,90){\line(-2,1){60}}
\put(120,90){\line(-6,1){180}}
\put(120,90){\line(-2,1){120}}
\put(-60,60){\line(-2,1){60}}
\put(-60,60){\line(2,1){60}}
\put(0,90){\line(-2,1){60}}
\put(0,0){\circle*{2}}
\put(0,-5){\makebox(0,0){$\scriptstyle 1$}}
\put(-60,30){\circle*{2}}
\put(-63,27){\makebox(0,0){$\scriptstyle 2$}}
\put(0,30){\circle*{2}}
\put(3,27){\makebox(0,0){$\scriptstyle 3$}}
\put(60,30){\circle*{2}}
\put(63,27){\makebox(0,0){$\scriptstyle 4$}}
\put(-120,60){\circle*{2}}
\put(-123,57){\makebox(0,0){$\scriptstyle 5$}}
\put(-60,60){\circle*{2}}
\put(-63,57){\makebox(0,0){$\scriptstyle 6$}}
\put(0,60){\circle*{2}}
\put(3,57){\makebox(0,0){$\scriptstyle 7$}}
\put(60,60){\circle*{2}}
\put(64,60){\makebox(0,0){$\scriptstyle 8$}}
\put(120,60){\circle*{2}}
\put(123,57){\makebox(0,0){$\scriptstyle 9$}}
\put(-120,90){\circle*{2}}
\put(-125,90){\makebox(0,0){$\scriptstyle 10$}}
\put(-60,90){\circle*{2}}
\put(-64,92){\makebox(0,0){$\scriptstyle 11$}}
\put(0,90){\circle*{2}}
\put(5,92){\makebox(0,0){$\scriptstyle 12$}}
\put(60,90){\circle*{2}}
\put(65,90){\makebox(0,0){$\scriptstyle 13$}}
\put(120,90){\circle*{2}}
\put(125,90){\makebox(0,0){$\scriptstyle 14$}}
\put(-60,120){\circle*{2}}
\put(-65,122){\makebox(0,0){$\scriptstyle 15$}}
\put(0,120){\circle*{2}}
\put(5,123){\makebox(0,0){$\scriptstyle 16$}}
\put(60,120){\circle*{2}}
\put(65,123){\makebox(0,0){$\scriptstyle 17$}}
\put(0,150){\circle*{2}}
\put(0,155){\makebox(0,0){$\scriptstyle 18$}}
\end{picture}
\caption{\protect\small A lower interval in a symmetric group}
\label{fig4}
\end{figure}

In order to give an example, let us consider the poset given in
Figure~\ref{fig4} (which is indeed a lower interval $[e,v]$ in a
Coxeter group). 
Then the pairing $\{  \{ 1,2 \}, \{ 3,7 \} , \{ 4,9 \} , \break
\{ 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.

\begin{Theorem} \label{thm2}
Let $W$ be a Coxeter group, $v\in 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)&\text{if }M(u)\lhd u,\\
qR_{M(u),M(v)}(q)+(q-1)R_{u,M(v)}(q)&\text{if }M(u)\rhd u.\end{cases}$$
\end{Theorem}

Theorem~\ref{thm2} implies immediately the Invariance
Theorem~\ref{thm1}. 


\section{The random assignment problem} \label{sec:RA}

The purpose of this section is to report the solution of the random
assignment problem by Linusson and W\"astlund (Link\"oping team), 
the origins of which lie in conjectures by M\'ezard and
Parisi \cite{MP85,P98}. 

Let $M$ be an $n\times n$ matrix of non-negative real numbers. 
An {\it assignment\/} is a selection of entries of $M$, such that we
take exactly one from each row and each column. A {\it minimum
assignment\/} is an assignment in which the sum of its entries is
minimal. Figure~\ref{fig5} shows a $4\times 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 with graph theory and combinatorial optimization
will realize that finding the minimum assignment in an $n\times 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}$.)

\def\Kreisum#1{\kern0pt#1\kern-2.5pt\raise3pt\hbox{\circle{14}}\kern-11pt}

\begin{figure}
$$\begin{matrix} 3&1&4&2\\
2&5&7&3\\
1&3&1&5\\
2&4&1&6\end{matrix}\quad \quad \quad 
\begin{matrix} \Kreisum3&1&4&2\\
2&5&\Kreisum7&3\\
1&3&1&\Kreisum5\\
2&\Kreisum4&1&6\end{matrix}\quad \quad \quad 
\begin{matrix} 3&\Kreisum1&4&2\\
2&5&7&\Kreisum3\\
\Kreisum1&3&1&5\\
2&4&\Kreisum1&6\end{matrix}
$$
\caption{\protect\small A matrix, an assignment, and a minimum assignment}
\label{fig5}
\end{figure}

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 non-rigorous) {\it replica
method}, M\'ezard and Parisi \cite{MP85} predicted that
\begin{equation} \label{eq:4} 
\lim_{n\to\infty}E(\text{min.\ assignment})=\frac {\pi^2} {6}.
\end{equation}
(Instead of the exponential distribution, they do in fact consider 
the uniform distribution on $[0,1]$, but, modulo physical intuition,
in the limit $n\to\infty$ this is equivalent.) Several years later,
Parisi \cite{P98} 
discovered that, apparently, there was a finite version of this
conjecture.

\begin{Conjecture} \label{conj2}
If the entries of an $n\times n$ matrix $M$ are chosen independently,
each according to the exponential distribution with mean $1$, then
$$E(\text{\em min.\ assignment})=1+\frac {1} {4}+\frac {1} {9}+\dots+\frac
{1} {n^2}.$$
\end{Conjecture}

Clearly, this is well in accordance with the prediction \eqref{eq:4}.

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\times 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
{\it $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\times 5$ matrix in Figure~\ref{fig6},
the circled elements mark a 2-assignment, which is in fact also a {\it
minimum} 2-assignment.

\begin{figure}
$$\begin{matrix} 3&1&4&2&4\\
2&5&7&3&1\\
1&3&1&5&6
\end{matrix}\quad \quad \quad 
\begin{matrix} 3&1&4&2&4\\
2&5&7&3&\Kreisum1\\
\Kreisum1&3&1&5&6
\end{matrix}
$$
\caption{\protect\small A rectangular matrix, and a minimum 2-assignment}
\label{fig6}
\end{figure}

Coppersmith and Sorkin \cite{CS98} came up with the following
surprising generalization of Conjecture~\ref{conj2}.

\begin{Conjecture} \label{conj3}
If the entries of an $m\times n$ matrix $M$ are chosen independently,
each according to the exponential distribution with mean $1$, then
$$E(\text{\em min.\ $k$-assignment})=
\sum _{i+j<k} ^{}\frac {1} {(m-i)(n-j)}.$$
\end{Conjecture}

It is not immediately obvious, but it is not too difficult to show, 
that for $m=n=k$
this implies Conjecture~\ref{conj2}.

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 {\it 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
\cite{BCR02}. 

\begin{Conjecture} \label{conj4}
If the entries of an $m\times n$ matrix $M$ are chosen independently,
the $(i,j)$-entry according to the exponential distribution with mean
$1/u_iv_j$, then
$$E(\text{\em min.\ $k$-assignment})=
\underset{Y\subseteq\{1,\dots,n\}}{\sum _{X\subseteq\{1,\dots,n\}}
^{}}\binom {m+n-1-\vert X\vert-\vert Y\vert}{k-1-\vert X\vert-\vert
Y\vert} \frac {(-1)^{k-1-\vert X\vert-\vert Y\vert}} {u_{\bar
X}v_{\bar Y}},$$
where $u_{\bar X}=\underset{i\notin X}{
\sum\limits _{i=1} ^{m}}u_i$, and similarly for $v_{\bar Y}$.
\end{Conjecture}

Again, it is not completely obvious but not too difficult to show that
Conjecture~\ref{conj4} implies Conjecture~\ref{conj3}, and thus
Conjecture~\ref{conj2}, see \cite{BCR02}. 

Now, a na\"\i 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},\dots,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 {\it in which some entries are fixed to be $0$}. Such a
formula was found, and proved, by Linusson and W\"astlund
\cite{LW03a}, see the theorem below. 
(It generalizes a previous one from \cite{LW03}, which was already
sufficient to prove Conjectures~\ref{conj2} and \ref{conj3}. We should
remark that a proof of the prediction \eqref{eq:4} was found earlier by Aldous
\cite{A01}, and that a proof of Conjectures~\ref{conj2} and
\ref{conj3} different from the one in \cite{LW03} has been 
found by Nair, Prabhakar and Sharma \cite{NPS03}.)

Here is the main theorem from \cite{LW03a}.

\begin{Theorem} \label{thm3}
Let $M$ be a (random) $m\times 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_iv_j$. Then
$$E(\text{\em min.\ $k$-assignment})=
\sum _{(X,Y)\in J_k(M)} ^{}\frac {-\mu\big((X,Y),\hat 1\big)} {u_{\bar
X}v_{\bar Y}}.$$
\end{Theorem}

Clearly, I need to explain the notation which is used in the statement
of the theorem.
A subset $\lambda$ of the rows and columns of $M$ is called
a {\it cover} if all entries of $Z$ are in $\lambda$. A
{\it$(k-1)$-cover} is one consisting of exactly $k-1$ rows and
columns. A {\it 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 $\hat J_k(M)$ be the poset consisting of the elements of
$J_k(M)$ ordered by inclusion, 
together with an artificial maximal element $\hat 1$. The function
$\mu(.,\hat 1)$ in the theorem denotes the {\it M\"obius function} on the
poset $\hat J_k(M)$, i.e., the function on $\hat J_k(M)$
which is uniquely determined by $\sum _{B\supseteq A} ^{}\mu(B,\hat
1)=\delta_{A,\hat 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\"obius 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\"onig's theorem on matchings and vertex
coverings in bipartite graphs, and an urn model invented by Buck, Chan
and Robbins in \cite{BCR02}. Again, it is not obvious that
Theorem~\ref{thm3} would imply Conjectures~\ref{conj2}--\ref{conj4},
but this is shown in \cite{LW03a}.



\section{The Charney--Davis and the Neggers--Stanley conjectures} \label{sec:5}

Here I report on progress made by Reiner and Welker (Marburg team),
and by Br\"and\'en (pre-doc in the network) on two tantalizing
conjectures in poset theory and the theory of simplicial complexes:
the {\it Neggers--Stanley Conjecture} and the {\it Charney--Davis
Conjecture}. I refer the reader to \cite{BretAH,StanAQ,StanAZ} 
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,\dots,n\}$. Let $\mathcal
L(P)$ denote its set of linear extensions, that is, the set of
$w=(w_1,w_2,\dots,w_n)\in S_n$ for which $i<_P j$ implies
$w^{-1}(i)<w^{-1}(j)$. The {\it$P$-Eulerian polynomial}
$$W(P,t)=
\sum _{w\in\mathcal L(P)} ^{}t^{\des(w)}$$
is the generating function for the linear extensions $w\in\mathcal L(P)$
counted according to the number of {\it descents} $\des(w)$, which is
the number of all $i$, $1\le i\le n-1$, such that $w_i>w_{i+1}$. 
This polynomial arose originally in the context of Stanley's theory of
$P$-partitions \cite{StanAB}, but has since then appeared and found
applications in many other situations. 

The Neggers--Stanley conjecture says the following.

\begin{Conjecture} \label{conj6}
For any labelled poset $P$ on $\{1,2,\dots,n\}$, the polynomial $W(P,t)$ has only
real (non-positive) zeroes.
\end{Conjecture}
Neggers had made this conjecture for {\it 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 \cite{BranAA,BranAB} 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 $\Delta$ 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 {\it$f$-vector} $(f_{-1},f_0,f_2,\dots,f_{d-1})$. The information
about the face numbers can also be equivalently, but very often more
conveniently, encoded by the {\it$h$-vector} $(h_0,h_1,\dots,h_{d})$,
defined by
$$
\sum _{i=0} ^{d}h_it^{d-i}=
\sum _{i=0} ^{d}f_{i-1}(t-1)^{d-i}.$$
We denote the polynomial $\sum _{i=0} ^{d}h_it^{i}$ by $h(\Delta,t)$.
The Charney--Davis Conjecture \cite[Conjecture~D]{ChDaAA} concerns the
evaluation of $h(\Delta, t)$ at $t=-1$ in the case where $d$ is even
and $\Delta$ is a {\it flag} simplicial homology $(d-1)$-sphere,
``flag" meaning that 
the minimal subsets of vertices which do {\it not\/} span a
simplex all have cardinality two.

\begin{Conjecture} \label{conj7}
When $\Delta$ is a flag simplicial homology $(d-1)$-sphere and $d$ is
even, then
$$(-1)^{d/2}h(\Delta,-1)\ge0.$$
\end{Conjecture}

In \cite{ReWeAA},
Reiner and Welker establish a link between these seemingly unrelated
conjectures. Let $P$ be a {\it 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
$\Delta_{eq}(P)$ of dimension $\vert P\vert-r-1$ (called the {\it
equatorial sphere}) such that
\begin{equation} \label{eq:7} 
W(P,t)=h(\Delta_{eq}(P),t).
\end{equation}
(Space does not permit to reproduce this construction here.)
Furthermore, by using the fact that $\Delta_{eq}(P)$ is the boundary of
a simplicial convex polytope, which makes it possible to apply
the $g$-Theorem \cite{StanAY} 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~\ref{conj6} for graded posets.
As a consequence, the Neggers--Stanley Conjecture for $P$ implies the
Charney--Davis Conjecture for $\Delta_{eq}(P)$, because it is
well-known that if $p(t)=p_dt^d+\dots+p_1t+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)\ge0$.
The paper \cite{ReWeAA} does in fact put forward evidence for the
thesis that both of the conjectures should be fruitfully viewed within
the context of {\it Koszul algebras}. It is worthwhile to point out
that this work inspired Athanasiadis \cite{AthaAA} 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 \cite{BranAA}, Br\"and\'en 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, {\it sign-graded\/} posets $P$.
Moreover, he is able to prove that $W(P,-1)$ has always the ``right" sign, so
that, via \eqref{eq:7}, the Charney--Davis Conjecture holds for all
the flag simplicial polytopal spheres $\Delta_{eq}(P)$. 

On the slightly negative side, Br\"and\'en constructs
counter-examples to the Neggers--Stanley Conjecture in
\cite{BranAB}. 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 still true. (In
fact, this is known for some already, see \cite{BranAA} for references.)
Also the Charney--Davis Conjecture may still be true in general.


\section{Map enumeration} \label{sec:maps}

The subject of this final section is the recent work by
Bousquet--M\'elou (Bordeaux team) and Schaeffer (Marne-la-Vall\'ee
team) on map enumeration.

A {\it 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 {\it faces} of the map.
For our purposes, the surface will always be the
plane. For such a {\it 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 {\it root edge} of the
map. Figure~\ref{fig7}.a shows a {\it rooted\/} planar map. The root
edge is indicated by the arrow.



\begin{figure}
%{\centering \epsfig{file=ex1.eps, width=10cm} \par}
{\centering \epsfig{file=ex2.eps, width=13cm} \par}
\caption{\protect\small A map, an Ising configuration, and a hard
particle configuration}
\label{fig7}
\end{figure}

In the {\it Ising model on maps}, one colours the vertices of the map
in two colours, black and white, say; 
see Figure~\ref{fig7}.b. (In the figure, ``bicoloured" edges, that is,
edges between
vertices of different colour are dotted.) The task is then to compute
the {\it partition function} (generating function, in combinatorial terms)
$$
\underset{\text{2-colourings of $m$}}{\sum _{m\in \mathcal C}
^{}}X^{\#\text{white vertices of $m$}}\,Y^{\#\text{black vertices of
$m$}}\, u^{\#\text{\text{bicoloured edges}}},$$
for a given class $\mathcal C$ of maps.

In the {\it 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~\ref{fig7}.c for an example. Here, the task is to compute
the partition function (generating function)
$$
\underset{\text{particle configurations}}{\sum _{m\in \mathcal C}
^{}}X^{\#\text{empty vertices of $m$}}\,Y^{\#\text{particles}},$$
for a given class $\mathcal 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.\
\cite{Brown-Tutte,Tutte,Tutte-planar}).
Among other things,
using the so-called {\it quadratic method\/} and {\it 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 \cite{Sch97,gillou}, by
constructing new bijections between maps and trees. On the physics
side, the idea of putting models on maps originates from
two-dimensional {\it quantum gravity} (see \cite{BIZ,BIPZ}). In many
cases, the physicists found (most of the time using matrix integrals;
see \cite{DiFrAA} for a recent survey)
nice algebraic partition functions. Again, the question arises why
these nice algebraic functions arise. Bousquet-M\'elou and Schaeffer
\cite{BoScAA} give the answer again in terms of bijections between
maps and trees. (This paper extends largely a previous one
\cite{BDFG02c} by Bouttier, Di~Francesco and Guitter, which is as well
based on ``Schaeffer-like" bijections.)

Bousquet-M\'elou and Schaeffer consider a very fine partition function
(generating function) for {\it 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
$$
{\sum _{m\text{ a bipartite map}}
^{}}
\prod _{i\ge1} ^{}x_i^{\#\text{white vertices of degree $i$ in $m$}}
\prod _{i\ge1} ^{}y_i^{\#\text{black vertices of
 degree $i$ in $m$}}.$$

The main theorem that they prove is the following.

\begin{Theorem} \label{thm4}
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
\begin{equation} \label{eq:8} 
y_2\big((W_0-B_2)^2+W_1-B_3-B_2^2\big),
\end{equation}
where the $W_i\equiv W_i(x_1,\dots,y_1,\dots)$ and 
$B_i\equiv B_i(x_1,\dots,y_1,\dots)$ are degree generating functions
for certain families of trees. The latter can be calculated from
the system of equations
\begin{equation*}
W_i = [z^{i}] \sum_{k\ge 0} x_{k+1} \Big(z+ B(z)\Big)^k,
\end{equation*}
and
\begin{equation*}
B_i = [z^{i}] \sum_{k\ge 0} y_{k+1} \left( \frac 1 z +
  W(z)\right) ^k,
\end{equation*}
where $W(z):= \sum_{i \ge 0 } W_i z^i$ and
$B(z):= \sum_{i \le 1 } B_i z^i$, and where 
$[z^{i}]S(z)$ denotes the coefficient of $z^i$ in the series $S(z)$.
\end{Theorem}

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
{\it polynomial\/} equations for the $W_i$'s and $B_i$'s. 
(As a consequence, the generating function in \eqref{eq:8} 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 \eqref{eq:8}
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 \cite{BK87}, while the second was originally
obtained, again in equivalent form, by Boulatov and Kazakov \cite{BDFG02a}.)

\begin{Corollary} \label{cor1}
The hard particle generating function for tetravalent maps (these are
maps in which all the vertices have degree $4$; see
Figure~{\em\ref{fig7}.a} for an example of such a 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^3yP^6}{(1-9xyP^2)^3}
$$
where $P\equiv P(x,y)$ is the power series defined by
$$
P=1+ 3xyP^3 + \frac {3xP^2}{(1-9xyP^2)^2}.
$$
\end{Corollary}


\begin{Corollary} \label{cor2}
The Ising generating function for bicoloured tetravalent maps
rooted at a white vertex is
\begin{multline*}
I(X,Y,u)=  \frac 1 9 \Big(
135x^2y^2P^6+72xy^2P^5
 -3y(15x+8y-3v^2y+36xy)P^4\\
\kern2.5cm -y(32+3v^2-36x -36y)P^3
 -(3+2v^2-72y)P^2
+12(1-3y)P -9 \Big)\\
 +\frac{(1-P-yP^2)(1+3yP)(12-8P+ 3v^2P)}{9(1+3xP)},
\end{multline*}
where $P\equiv 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} $.
\end{Corollary}

The proof of Theorem~\ref{thm4} 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~\ref{fig8}), 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~\ref{fig8}), in which case we end
up with one map which contains two pending (half-)edges.

\begin{figure}
%{\centering \epsfig{file=ex1.eps, width=10cm} \par}
{\centering \epsfig{file=rooted.eps, width=13cm} \par}
\caption{\protect\small Cutting the root edge}
\label{fig8}
\end{figure}

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


\begin{figure}
{\centering \hbox{\epsfig{file=ex3.eps, width=19cm}} }
\caption{\protect\small A blossom tree}
\label{fig9}
\end{figure}

Given a blossom tree, one can construct a map by the following {\it
closure procedure}. Starting from the root, we go around the tree, and,
whenever we encounter a bud immediately followed by a leaf, we connect
the two by an edge. See Figure~\ref{fig10} for an example.

\begin{figure}
{\centering \hbox{\epsfig{file=closure.eps, width=14cm}} }
\caption{\protect\small The closure of a blossom tree}
\label{fig10}
\end{figure}

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~\ref{thm4}.


\begin{thebibliography}{10}

\bibitem{A01} D. Aldous, \emph{The $\zeta(2)$ limit in the random
assignment problem}, Random Structures Algorithms {\bf 18} (2001),
381--418.

\bibitem{AS02}
S. E. Alm and G. B. Sorkin, \emph{Exact expectations
and distributions in the random assignment problem}, Combin.
Probab.\ Comput.\ {\bf 11} (2002), 217--248.

\bibitem{AthaAA}C. Athanasiadis, {\em Ehrhart polynomials, simplicial
polytopes, magic squares and a conjecture of Stanley}, preprint, 2003;
{\tt math.CO/0312031}.

\bibitem{BB}
A. Beilinson and J. Bernstein,
{\em Localisation de $g$-modules}, 
C. R. Acad.\ Sci.\ Paris {\bf 292} (1981), 15--18. 

\bibitem{BIZ}
D.~Bessis, C.~Itzykson and J.~B. Zuber, {\em Quantum field theory
techniques in graphical enumeration},  Adv.\ Appl.\ Math.\ {\bf
1}(2) (1980), 109--157.

\bibitem{BL}
S. Billey and V. Lakshmibai,  {\em Singular loci of Schubert varieties}, 
Progress in Math.\ {\bf 182}, Birkh\"{a}user, Boston, MA, 2000. 

\bibitem{BK87}
D.~V. Boulatov and V.~A. Kazakov, {\em The {I}sing model on a random
planar lattice: the structure of the 
  phase transition and the exact critical exponents},
Phys.\ Lett.~B {\bf 186}(3-4) (1987), 379--384.


\bibitem{BoScAA} M.  Bousquet-M\'elou and Schaeffer, {\em The degree
distribution in bipartite planar maps: applications to the 
Ising model}, preprint, 2003; {\tt math.CO/0211070}.

\bibitem{BDFG02a}
J.~Bouttier, P.~Di~Francesco and E.~Guitter, {\em Critical and
tricritical hard objects on bicolourable random 
  lattices: exact solutions}, J. Phys.~A {\bf 35}(17) (2002),
3821--3854.

\bibitem{BDFG02c}
J.~Bouttier, P.~Di Francesco and E.~Guitter,
{\em Census of planar maps: from the one-matrix model solution to a
combinatorial proof}, Nucl.\ Phys.\ {\bf B645} (2002), 477-499.

\bibitem{BranAA}P. Br\"and\'en, {\em Sign-graded posets, unimodality
of W-polynomials and the Charney--Davis Conjecture}, preprint, 2004;
{\tt math.CO/0406019}.

\bibitem{BranAB}P. Br\"and\'en, {\em Counterexamples to the
Neggers--Stanley conjecture}, preprint, 2004; 
{\tt math.CO/0408312}.

\bibitem{BretAH} F.    Brenti, {\em Log-concave and
unimodal sequences in algebra, combinatorics, and geometry: an
update}, Contemp.\ Math.\ {\bf 178} (1994), 71--89.

\bibitem{BretAZ} F. Brenti, {\em Kazhdan-Lusztig polynomials: History,
Problems, and Combinatorial Invariance}, S\'eminaire Lotharingien
Combin.\ {\bf 46} (2003), Article~B46c, 30~pp.

\bibitem{BretAY} F. Brenti, {\em The intersection cohomology of
Schubert varieties is a combinatorial invariant},
Europ.\ J. Combin.\ {\bf 25} (2004), 1151--1167.

\bibitem{BrCMAA} F. Brenti, F. Caselli and M. Marietti,  
{\em Special matchings and Kazhdan-Lusztig 
polynomials for doubly laced Coxeter systems}, preprint, 2003.

\bibitem{BIPZ}
E.~Br{\'e}zin, C.~Itzykson, G.~Parisi and J.~B. Zuber, {\em 
Planar diagrams}, Comm.\ Math.\ Phys.\ {\bf 59}(1) (1978), 35--51.


\bibitem{Brown-Tutte}
W.~G. Brown and W.~T. Tutte, {\em On the enumeration of rooted
non-separable planar maps},  Canad.\ J. Math.\ {\bf 16} (1964), 572--577.

\bibitem{BK}
J.-L. Brylinski and M. Kashiwara, {\em Kazhdan-Lusztig conjecture and 
holonomic system}, Invent.\ Math.\ {\bf 64} (1981), 387--410.

\bibitem{BCR02} M. W. Buck, C. S. Chan and D. P. Robbins, 
\emph{On the expected value of the minimum assignment}, Random
Structures Algorithms {\bf 21} (2002), 33--58.

\bibitem{ChDaAA}R. Charney and M. Davis, {\em Euler characteristic of
a nonpositively curved, piece-wise Euclidean manifold}, Pacific
J. Math.\ {\bf 171} (1995), 117--137.

\bibitem{Cloux}F. du Cloux,
{\em Rigidity of Schubert closures and invariance of Kazhdan-Lusztig
polynomials}, 
Adv.\ in Math.\ {\bf 180} (2003), 146--175.

\bibitem{CS98}
D. Coppersmith and G. B. Sorkin, \emph{Constructive bounds and exact
expectations for the random assignment problem}, Random Structures 
Algorithms {\bf 15} (1999), 133--144.

\bibitem{Dela}E. Delanoy, {\em Invariance combinatoire des polyn\^omes
de Kazhdan--Lusztig sur les intervalles partant de l'origine},
preprint, 2003; {\tt math.CO/0312237}.

\bibitem{DiFrAA} P. Di Francesco,
{\em 2D quantum gravity, matrix models and graph combinatorics},
preprint, 2004; {\tt math-ph/0406013}.

\bibitem{Dye1}M. J. Dyer,
{\em  On the "Bruhat graph" of a Coxeter system},
Compositio Math.\ {\bf 78} (1991), 185--191.

%\bibitem{Dye97}
%M. J. Dyer, 
%{\em On coefficients of $q$ in Kazhdan-Lusztig polynomials}, 
%Algebraic groups and Lie groups, 
%Austral. Math. Soc. Lect. Ser. {\bf 9}, 
%Cambridge Univ. Press,
%Cambridge, 1997, 189--194.

\bibitem{FKK}
I. Frenkel, M. Khovanov and A. Kirillov,  
{\em Kazhdan-Lusztig polynomials and canonical basis}, 
Transform.\ Groups {\bf 3} (1998), 321--336. 

\bibitem{FultAC} W.    Fulton, {\em Young tableaux}, Cambridge
University Press, Cambridge, 1997.

\bibitem{FuHaAA}
W. Fulton and J. Harris,
{\em Representation Theory},
Springer--Verlag, New York, 1991.

\bibitem{Ha}
M. Haiman,  {\em Hecke algebra characters and immanant conjectures}, 
J. Amer.\ Math.\ Soc.\ {\bf 6} (1993), 569--595.

\bibitem{HumpAC}
J. E. Humphreys, {\em Reflection groups and Coxeter groups}, 
Cambridge University Press, Cambridge, 1990.

\bibitem{K-L}
D. Kazhdan and G. Lusztig, {\em Representations of Coxeter groups
and Hecke algebras}, Invent.\ Math.\ {\bf 53} (1979), 165--184.

\bibitem{KL2}
D. Kazhdan and G. Lusztig, {\em Schubert varieties and Poincar\'{e}
duality}, Geometry of the Laplace operator, Proc.\ Sympos.\ Pure
Math.~34, Amer.\ Math.\ Soc., Providence, RI, 1980, pp.~185--203.

\bibitem{La-Se}
V. Lakshmibai and B. Sandhya, {\em Criterion for smoothness
of Schubert varieties in $S_{l(n)/B}$}, Proc.\ Indian Acad.\ Sci.\
Math.\ Sci.\ {\bf 100} (1990), 45-52.

%\bibitem{LW00} Linusson, Svante and W\"astlund, Johan, \emph{A
%generalization of the random assignment problem},
%arXiv:math.CO/0006146. unpublished preprint.

\bibitem{LW03} S. Linusson and J. W\"astlund,
\emph{A proof of Parisi's conjecture on the random assignment
problem},  Probab.\ Theory Related Fields  {\bf 128}  (2004), 419--440.

\bibitem{LW03a} S. Linusson and J. W\"astlund,
\emph{A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem}, preprint; {\tt math.CO/0307357}.

\bibitem{MP85} M. M\'ezard and G. Parisi, {\em Replicas and
optimization}, J. Phys.\ Lett.\ {\bf 46} (1985), 771--778.

\bibitem{NPS03} C. Nair, B. Prabhakar and M. Sharma,
\emph{A proof of the conjecture due to Parisi for the finite random
assignment problem}, preprint, 2003; available at
{\tt http://www.stanford.edu/\~{}balaji/rap.html}.

\bibitem{P98} G. Parisi, {\em A conjecture on random bipartite
matching}, manuscript, 1998;
{\tt cond-mat/9801176}.

\bibitem{ReWeAA} V. Reiner and V. Welker, {\em On the Charney-Davis
and Neggers-Stanley conjectures}, preprint, 2002; available from
{\tt http://www.mathematik.uni-marburg.de/\~{}welker}.

\bibitem{SagaAQ}
B.~E. Sagan, {\em The symmetric group}, 2nd edition,
Springer--Verlag, New York, 2001.

\bibitem{Sch97}
G.~Schaeffer, {\em Bijective census and random generation of
{E}ulerian planar maps with prescribed vertex degrees},
Electron.\ J. Combin.\ {\bf 4}(1) (1997), \#R20, 14~pp.

\bibitem{gillou}
G.~Schaeffer, {\em Conjugaison d'arbres et cartes combinatoires
al\'eatoires}, Ph.D. thesis, Universit\'e Bordeaux 1, France, 1998.

\bibitem{StanAB} R. P. Stanley, {\em Ordered structures and
partitions}, Mem.\ Amer.\ Math.\ Soc.\ No.~119,
Amer.\ Math.\ Soc., Providence, R.~I., 1972.

\bibitem{StanAY}R. P. Stanley, {\em  The number of faces of a
simplicial convex polytope}, Adv.\ in Math.\ {\bf 35} (1980), 236--238. 

\bibitem{StanAQ} R. P. Stanley, {\em Log-concave and
unimodal sequences in  algebra, combinatorics, and geometry},
Ann.\ New York Acad.\ Sci.\ {\bf 576} (1989), 500--534.

\bibitem{StanAZ}R. P. Stanley, {\em Combinatorics and commutative
algebra}, 2nd edition, Birkh\"auser, Basel, 1996.

\bibitem{Tutte}
W.~T. Tutte, {\em A census of planar maps},
Canad.\ J. Math.\ {\bf 15} (1963), 249--271.

\bibitem{Tutte-planar}
W.~T. Tutte, {\em On the enumeration of planar maps}, 
Bull.\ Amer.\ Math.\ Soc.\ {\bf 74} (1968), 64--74.

\bibitem{Ug}
D. Uglov, {\em Canonical bases of higher level $q$-deformed Fock
spaces and Kazhdan-Lusztig polynomials}, Physical Combinatorics, 
Progress in Math., {\bf 191}, Birkh\"{a}user, Boston, MA, 2000, 249--299.

\end{thebibliography}

\end{document}



