MARS

MARS

Le projet détaillé

Objectifs et contexte

First, we briefly recall the story of the ubiquitous sequence 1,2,7,42,429,.. that is the story of the famous alternating sign (ex-)conjecture in Combinatorics and of the more recent Razumov-Stroganov conjecture in Theoretical Physics.

Alternating sign matrices (ASM) have been introduced in 1982 by B.Mills, D.Robbins and H.Rumsey (Princeton) in relation with a method for computing determinants due to C.Dodgson (aka Lewis Caroll) in 1866 and called “condensation of determinants”. ASM are nxn matrices, whose entries are 0,1,-1 and such that each row or column sum is 1 and such that the non-zero entries “alternate” in row and column. Permutations form a subclass (no occurrences of -1). Mills, Robbins and Rumsey found empirically a nice formula for the number A(n) of such matrices as a ratio of product of some factorials. This is the famous alternating sign conjecture. A refined version was a formula for the enumeration of such matrices according to n and the position of the (unique) 1 in the first row.

The context was the theory of plane partitions (PP). This domain was initiated by the Major Percy A. MacMahon. Plane partitions are 3D analog of Ferrers diagrams (aka Young diagrams, or partitions of an integer). They are related to Young tableaux involved in the representation of the symmetric group. MacMahon gave in 1912 a formula for the q-number of plane partitions contained in an nxnxn box, and conjectured a formula for the q-number of such partitions which are symmetric under the exchange of two axes. This formula was proved by G.Andrews and I.Macdonald (independently) in 1979. Then cyclically symmetric partitions were introduced and a conjectured formula was stated by Macdonald in 1979. In relation with this conjecture, G.Andrews introduced the notion of descending plane partitions (DPP) and gave a q-counting formula for the enumeration of such partitions. Surprisingly DDP and ASM are enumerated by the same number , but today no bijection has been given. Mills, Robbins and Rumsey proved Macdonald conjecture in 1982.

Several other symmetries for plane partitions were systematically investigated, and experimental formulae were discovered. Up to isomorphism, a total of ten classes was listed by Richard Stanley in 1985. The more profound and more surprising of all of them are the class of partitions having all possible symmetries, they are the famous totally symmetric self-complementary plane partitions (TSSCPP) and in 1983, Mills ,Robins and Rumsey discovered experimentally that they were enumerated by the same number A(n) as for the ASM.

Some important combinatorial steps were made at that time in this domain. Gessel and Viennot showed that Young tableaux and various classes or planes partitions can be encoded by configurations of non-crossing paths in the discrete plane, and also popularized the so-called “Linström-Gessel-Viennot” methodology (LGV) saying that in general non-crossing configurations of paths can be enumerated by a determinant (and more generally weighted paths). Such methodology appeared independently in theoretical chemistry, in probability theory with Karlin-MacGregor determinants for birth and death process, and in physic: “vicious walkers” for wet transition introduced by M.Fisher and systems of free fermions (their (Slater) waves functions and their grand canonical partition function can be expressed as determinants) . Another important advance was made by Kuperberg by giving correspondence between plane partitions and tilings of triangular lattice, or equivalently configurations of dimers on a honeycomb grid, which can be enumerated applying the Pfaffian or permanent method as introduced by Kastelyn and al, and successfully applied in the 60’s for the Ising model. In general the difficulty comes in expressing such determinant or Pfaffian in term of formulae as a product divided by a product. A typical example is the content/hook length formula for the number of Young tableaux of given shape. More difficult is when the configuration of non-crossing paths has some variables ending or starting points. The number becomes a sum of determinants. J.Stembridge's classical paper (1990), with insight of B.Gordon and S.Okada, reduces this sum to a single Pfaffian.

With such preliminary tools, two major breakthrough appear in 1992: G. Andrews proved the formula for the number of TSSCPP and D.Zeilberger announced a proof of the ASM conjecture. The first step was to put in bijection the TSSCPP with some families of paths, this was done by S.Dulucq in his thesis at Bordeaux in 1986 and rediscovered by W.Doran in 1989. Andrews started with the corresponding Stembridge Pfaffian, and after several “tour de forces”, computer manipulations, the problem was transposed into the world of hypergeometric functions with a new identity proved by the classical WZ-methodology. Then D.Zeilberger gave in 1996 the first complete proof of the ASM by showing that their number was the same as the number of TSSCPP. The paper is another “tour de force”, with 84 pages of residues calculus, constant term identities and the help of 70 “checkers”. Today, no bijections is known between TSSCCPP and ASM.

Another breakthrough came in 1996 with a second proof by G.Kuperberg of the ASM conjecture, showing the equivalence of ASM with the square ice model, aka the 6-vertex model in statistical mechanics with some domain wall boundary conditions (DWBC). The solution reduces to the calculation of a quantum determinant of A.Izergin and V.Korepin, in relation with “scattering inverse methods” in quantum physics. D.Zeilberger uses this determinant to prove the “refined” ASM conjecture. Systematic studies were given for the ten classes of symmetries for PP with major determinant-Pfaffian methodology developed by C.Krattenthaler and his Wien school solving related or variation of the main models.

About 2001-02 came another big surprise, in a completely different context from quantum physics of spin chains. A.Razumov and Y.Stroganov considered anti ferromagnetic XXZ periodic chains for delta=-1/2. They discovered that the components of the ground state vector, with proper normalisation, were integers related to ASM. Equivalently, Batchelor, de Gier and Ninhuis considered the dense 0(1) loop model on a cylinder and the corresponding Hamiltonian expressed in term of the sum of the basis of the Temperley-Lieb algebra. They discovered that the sum of the coefficients of the ground state vector, or Perron-Frobenius eigenvector, suitably normalized, were precisely the number of ASM. This is the so-called “weak” version of the Razumov-Stroganov conjecture, and has been proved by the French physicists P. Di Francesco and P.Zinn-Justin in 2004 (with multi-parameter rule), using familiar tools such as transfer matrix method and Yang-Baxter equation.

The (strong) Razumov-Stroganov conjecture (RS) gives interpretation of the individual terms of the Perron-Frobenius eigenvector in term of “arch patterns”, or configuration of non crossing lines joining 2n points of a circle (enumerated by Catalan numbers). To each ASM, one associates bijectively an FPL (Fully Packed Loop) on an nxn grid via the connection with the 6-vertex model with DWBC. Each term of the eigenvector corresponds to an arch pattern and the RS conjecture says that the corresponding coefficient is precisely the number of FPL associated to that pattern. With different boundary conditions, one gets similar conjectures involving some classes of ASM or of PP with certain symmetries.

A big challenge is to give a proof of the (strong) RS conjectures. An objective of the project is to do some progress in a combinatorial approach of both weak and strong RS conjectures. In the same spirit, we also plan to make some progress toward a combinatorial comprehension of the connection between ASM and TSSCPP and, maybe, to solve the longstanding challenge to find a bijection between these two classes of objects.

Around the main topics of the PP, ASM, TSSCPP, FPL, RS conjecture, much more connections with other domains of algorithmics, combinatorics, mathematics and physics, have appeared since 1980. First, ASM are related to the growing domain of “random discrete structures”, random tilings, or such methodology as “coupling from the past”, Markov chains (J.Propp and Wilson). Another domain is in algebraic combinatorics, particularly developed by the Marne-le-Vallée team, with the theory of symmetric functions, the introduction by Lascoux and Schützenberger of the Schubert and Grothendieck polynomials . Many work has been done (see monograph of Macdonal or Manivel), in relation with Yang-Baxter coefficients. Extension of RS conjectures has been given by Di Francesco and Zinn-Justin for the loop model on a cylinder with crossings, and Schubert polynomials appear with integers interpreted as dimension of orbital varieties related to some Lie algebras. Strong relation with symmetric group and Coxeter groups exists. Lascoux and Schützenberger introduced a completion of the Bruhat (Ehresmann) order of the symmetric group into a distributive lattice. The elements of this lattice are in bijection with the ASM. Other connections are orthogonal polynomial theory: number of ASM and PP are related to Hankel determinants (Tramm 2001, Gessel-Xin 2005). Also the so-called 1-, 2- 3- enumeration of AMS involve respectively continuous Hahn, Meixner-Pollaczek and continuous dual Hahn polynomials,(F.Colomo, A.G.Pronko, 2004,2006).

A third objective is to develop these different connections and to give us better tools to attack the two main challenges: RS and ASM-TSSCPP.

Description du projet et résultats attendus

We have described above a summary of the tremendous works made around PP, (plane partitions), DPP (descending plane partitions), ASM (alternating sign matrices), TSSCPP (totally symmetric self-complementary plane partitions) and RS (strong Razumov-Stroganov conjecture), since 25 years by various people from combinatorics, mathematics and physics, some of them being considered as the “popes” or top leaders in their domain. A book has been written by D. Bressoud “Proofs and confirmations: the story of the alternating matrices conjectures” 1999 (before the appearance of the RS conjecture). At that time most of the conjectured formulae about PP and ASM were proved, often with very laborious and ad hoc calculations. But , as said D.Bressoud at the end of an AMS conference given in November 2005: this is really just the beginning. Despite these 25 years of efforts, a combinatorial explanation or a general framework for the whole story is missing. Four classes of objects are enumerated by the same number A(n): DPP, ASM, TSSCPP and the RS coefficients and not a single bijection, even no beginning of a combinatorial explanation is known today. Even the factorials appearing in the numerator and the denominator of the product formula for A(n) do not have natural interpretation or appearance in the nowadays zoo of known combinatorial objects.

So it may appear very pretentious to propose an ambitious project attacking the two main challenges: prove with combinatorial tools the (strong) RS conjecture (Razumov-Stroganov) and construct a bijection between the ASM (alternating sign matrices) and the TSSCPP (totally symmetric self-complementary plane partitions).

At least, we are convinced that we can make some significant progress around the combinatorial comprehension of RS and ASM because of the variety of competence of the members of the team. Each of the related domain is represented by some members of the group. The necessary related domains include: algebraic combinatorics (A.Lascoux, J.C.Aval and X.G.Viennot, with symmetric functions, Schur, Schubert and Grothendieck polynomials, combinatorial Hopf algebras, ..), bijective and enumerative combinatorics (X.G.Viennot and most of the bordelais group), “ALEA” , random discrete structure, Markov chains, etc.. (P.Duchon, J.F.Marckert), experimental combinatorics (algebraic with software ACE A.Lascoux, and “visualization” or “bijective” experimentation in Bordeaux), combinatorial theory of orthogonal polynomials (A.Lascoux and X.G.Viennot), q-series and q-calculus (most members). Also, in the RS conjecture, there are different appearance of objects enumerated by Catalan numbers (arch systems, basis of the Temperley-Lieb algebra, etc ..). A specialty of the Bordeaux team, especially Y. Le Borgne and X.G.Viennot is to have a profound knowledge of the deepest aspects of the so-called Catalan garden.

Their are some important “physics” aspects in the project. Some members of the group also have a “physics” competence, as shown by their publications in various Physics Journals, or being invited in some Physics conferences. Since many years, we had some relation with the Theoretical physics group of the CEA in Saclay, in particular with the “regretté” Claude Itzykson. We have some contacts or discussions with Di Francesco and his group with Guitter and Bouttier. The trio Di Francesco (Saclay), J.B.Zuber (Paris 6), Zinn-Justin (Orsay) has been very active in the RS-ASM-PP domain and have published more than a dozen of deep and profound papers in the last few years (see all of them on ArXiv). In this project we plan to have more exchanges and collaborations with these physicists. Other physicists in France working in this RS domain are Kitanine (“médaille de bronze CNRS”), with Maillet in the theoretical physics group of ENS Lyon. Also,the bordeaux team has a long and strong cooperation with two other physics centers in the world: the theoretical group at the Tata Mumbai in India (Deepak Dhar) and the Melbourne group of Statistical mechanics directed by A.Guttmann (several visits and exchanges between both Bordeaux and Melbourne, with two thesis in co-tutelle). The Marne-la-Vallée group also has many exchange with physicists, especially with Melbourne, Tianjin and Kyoto.

Thus the project has a strong interdisciplinarity, covering in fact three sectors: computer science, mathematics and physics. The group has strong competences in the three sectors, the collaboration on various topics between the different members has a long and strong history, making the team probably unique in the world and justifies the conviction to bring something new in these difficult challenges. But there is more.

Recently, P.Duchon conjectured a slightly stronger RS-conjecture which can be described from Markov chain into a pure combinatorial form on the FPL and arch diagrams. The formulation is in term of finding a bijection on FPL satisfying certain invariance properties when projected onto arch diagrams. In collaboration with J.F Marckert,he made some progress in the search of such a bijection.

We also plan to get some interactions with theoretical computer science. For example the theory of Françon‘s “data histories”, with application to computing integrated cost in data structures (work of Françon, Flajolet, Vuillemin in the 80’s), in connection with combinatorial theory of orthogonal polynomials, would probably be a source of inspiration for an operator approach of our project. Compared to other concurrent groups in Physics or in Mathematics, a unique advantage of our team, is to be embedded in the French “STIC” culture, that is to be also computer scientists, collaborating with our colleagues of our respective computer science laboratory both in LaBRI at Bordeaux and at the IGM in Marne-La-Vallée.

The methodology of our project is clear and detailed below: first develop as much as possible the combinatorics of the related domains and introduce new combinatorial tools, with a strong help from experimental combinatorics (both “formal algebraic” and “visual”) and then, with this enlarged vision attack combinatorially the (weak and strong) RS conjecture and its extensions. Then, after a happy RS achievement, a new vision should emerge and enable us for finding the missing bijection between ASM and TSSCPP.

1 - Hypercube, Associahedron, Permutohedron and alternatohedron.

The permutohedron is the polytope or the poset formed by the n! permutations ordered by the (weak) Bruhat order. The edges correspond to the “covering” relation between two elements. There is also the order introduced by Ehresmann, also called (strong) Bruhat order. Considerable work has been done in algebraic combinatorics about this permutohedron, in relation with algebraic geometry and the combinatorics of Coxeter groups, in particular by A.Lascoux and M.P.Schüteznberger. See for example the recent book of A.Björner and F. Brenti.

A major advance in the ASM domain was made by A.Lascoux and M.P.Schützenberger with the introduction of an embedding of the permutohedron ordered by the (strong) Bruhat order into a distributive lattice, where the concept of “key” of a permutation, going back to Ehresmann, plays a central role. The vertices of this new lattice are in fact the “monotone triangles” which are well-known to be in bijection with the ASM (the bijection is easy). This remarkable construction has not yet be fully developed.

In another context, some recent researches in different parts of mathematics and combinatorics , in particular by J.L.Loday in Strasbourg, have shown the growing importance of the structure called associatohedron (see for example the survey paper of J.L. Loday related to the colloquium given at the Clay Mathematics Institute in 2005). The vertices of the associahedron are in bijection with binary trees (aka Dyck words in computer science, or triangulations of a regular polygon in combinatorics), that is are enumerated by the Catalan number. The associatohedron is a poset for a certain order relation, the “Tamari lattice”. It is also a cellular complex isomorphic to the “Stasheff polytope” which plays a key role in the characterization of spaces homotopically equivalent to loop spaces. Tamari lattice and associatohedron are strongly related to the now classical Loday-Ronco algebra among binary trees. This algebra is a dendriform algebra (as introduced by Loday, even it is the free dendriform algebra on one generator) is in fact a Hopf algebra. As the Connes-Kreimer Hopf algebra, it is related to renormalization theory in quantum physics and noncommutative geometry.

Some work of J.L.Loday, P.Palacios and M.Ronco gives some interesting relations between the permutohedron, the associatohedron and the hypercube. This last structure is the word of “up-down” sequence of permutations, counted by 2^n, or word in two letters. The authors show that each structure can be “projected” onto the other, starting from permutations, to binary trees, and then to binary words, such that the (weak) Bruhat order becomes the Tamari order on binary trees, and then becomes the lexicographic order on words.

Now, from Lascoux-Schützenberger construction, monotone triangles, and thus ASM are naturally ordered and the analogue situation arose, with a “projection” from the ASM lattice to the permutohedron such that the order on ASM becomes the (strong) Bruhat order on permutations. We propose to call the L-S lattice of ASM the “alternatohedron”.

This leads us to the first objective of the MARS project:

Objective1.Construct a unified theory of the relative embedding of the four complexes: hypercube, associatohedron, permutohedron, altenatohedron and of the corresponding Hopf algebras.

In particular, it would be nice to find a projection of the alternatohedron to the associatohedron, via the permutohedron, such that the ASM is sent onto its corresponding FPL (fully packed loop) via the process described above in B1 with the six-vertex model and the RS conjecture.

Another direction of researches would be to define a Hopf algebra structure on the alternatohedron, in an analogous way of the corresponding Hopf algebra for the other three levels: hypercube with the Solomon descent algebra, (or Hopf algebra of non commutative symmetric functions, dual of the Hopf algebra of quasi-symmetric functions, which begin to play important role in combinatorics), the Loday-Ronco Hopf algebra of binary trees and at the level of permutations the Malvenuto-Reutenauer Hopf algebra of permutations. J.C.Aval, member of the Bordeaux group, has been classified by R.Stanley (MIT) as one the best worldly specialist of the young generation in this new growing domain in combinatorics and mathematics (see for example a Banff workshop on combinatorial Hopf algebras). Even if Aval’s thesis was made in the mathematics department of Bordeaux, the subject was in fact coming form the Californian school of algebraic combinatorics around A.Garsia and the famous “ n! conjecture” and from the Canadian school under N.Bergeron (York, Toronto) and F.Bergeron (LACIM, Montréal) with combinatorial Hopf algebra.

Remark, that another important recent trend in Mathematics was the introduction by S.Fomin and A.Zelevinski of the new field of “cluster algebras”. The starting point was the associatohedron, with vertices indexed by triangulations of a regular polygon with two by two non intersecting diagonals (in bijection with binary trees). In fact this was the historical introduction of the “Catalan numbers”, going back to Euler and Segner in the years 17.. and later around 1830 by many people including Binet, Liouville, Catalan (calling these numbers Segner numbers), with some table of Arbogast (Strasbourg) around 1800. It is easy to go from one triangulation to another by a sequence of “flips” of diagonals in rectangles. This is the starting of an axiomatization which leads Fomin and Zelevinski to the theory of cluster algebras. They appear as a new and important domain of mathematics, with many connections with different fields. A classification of cluster algebras has been made, analogous to the one of Coxeter groups or root systems (see for example the recent school at the French CIRM organized by Leclerc and Chapoton). Flip also exists at the other level of word, permutations and alternatohedron. Another part of the objective one, is to study these flips on the ASM and the resulting cluster algebra.

This leads us to the combinatorics of Catalan numbers and the “Catalan garden”.

2 - The Catalan garden

We just described in the previous section the important role of the associatohedron in our ASM context. The number of vertices are the Catalan numbers. In the RS conjecture context, different combinatorial objects counted by the Catalan numbers appear. For example the “arch systems” associated to the FPL. Also the Temperley-Lieb algebra plays a central role in the formulation of the RS conjecture. Such algebra with n generators has dimension the Catalan numbers C_n. Temperley-Lieb algebra were introduced in statistical physics, in relation with the Potts model.

Also in the TSSCPP context, with Dulucq's bijection, such partitions are in one-to-one correspondence with some configurations of non-intersecting paths. Such configurations correspond to some minor of a certain matrix formed by binomial coefficients. The sum of such minor is A(n). It was a conjecture of M.P.Schützenberger , (proved by S.Dulucq in his thesis 1986) that the number of non zero minor was the Catalan number, that is the number of possibles configuration of starting and ending points of the paths. As shown by a recent paper of Di Francesco (2004) about a refined RS conjecture, it is of importance to relate the two appearances of Catalan numbers in the combinatorics of FPL (aka ASM) and of TSSCPP. A better understanding would help toward the discovery of the missing bijection between ASM and TSSCPP. This leads us to the second objective of the project:

Objective 2 -Develop a better understanding and find combinatorial connections between the different appearance of objects counted by Catalan numbers in the TSSCPP, ASM and RS conjecture context.

We should add that in the seminal paper of Gessel and Viennot (Binomial determinants, Adv in Maths, 1985), we have different configuration of non-crossing paths, corresponding to the minor of the matrix formed by the first n rows and columns of the Pascal triangle arranged in the classical way (with zeros above the diagonal). The number of non-zero minors is also the Catalan numbers. The underlying combinatorics is the one of standard and semi-standard Young tableaux, leading to an “almost” bijective proof of the classical “content/hook lengths” formula for the number of Young tableau of given shape. It is well known that pure bijective proof for such hook -length formula are really difficult (see for example the one of C.Krattenthaler). We believe that a bijective proof for the formula giving the number A(n) of ASM would be at a level much more higher.

Meanwhile, we can progress towards this “Himalayan” level by practicing within our Pyrénéan mountains with our deep knowledge of the so-called “Catalan garden”, that is all the different objects enumerated by Catalan numbers and their related bijections (some are easy and classical, some are much deeper). Classical and well known interpretation are triangulations of regular polygons, binary trees , forests of planar trees, Dyck words, arch diagrams, 2-colored Dyck paths, and less classical such as: semi-pyramid of dimers on the positive integers, triangular lattice directed animals with half width equal to zero, or some Lorentzian triangulations coming from 2D quantum gravity (Di Francesco, Kristanjen, Guitter and Viennot).

In our bordelais group, X.G.Viennot, N.Bonichon and Y.Le Borgne are specialists of such Catalan bijections and have shown that some deep constructions, and even, still open questions, remain in this Catalan Garden. In particular, Bonichon’s thesis is about the so-called Schnyder trees and their use for drawing and visualization of graph. They form a very interesting combinatorial structure. Their number is given by a formula of the type product divided by a product, they are in bijection with pair of non-intersecting Dyck paths. For such bijection, Bonichon introduced some flips, analogous to the one defined for triangulations of regular polygons and related to some Fomin-Zelevinsky cluster algebra. In fact Schnyder tree form a graph with edges in 3 colors. For each color, the underlying subgraph is an associatohedron; using two color gives rise to a poset. A (general) triangulation is underlying each Schnyder tree.

So, a sub-objective of objective 2, would be to develop the combinatorics of Schnyder trees, in the context of the associatohedron, cluster algebras, and the connections with the permutohedron and associatohedron, as described in objective 1.

Another possible direction to explore would be the connection between Temperley-Lieb algebra and the theory of heaps of pieces. In an unpublished manuscript, Fomin and Viennot have develop this topic. They introduce another algebra called nil-Temperley-Lieb, having the same dimension (Catalan number) and same basis as the classical Temperley-Lieb algebra. Such basis can be described as certain heaps of dimers of a segment of length n. The general theory of heaps of pieces was introduced by the coordinator of the project in 1985, as a geometrico-combinatorial interpretation of the so-called commutation monoids introduced by P.Cartier and D.Foata in 1969. Heaps of pieces theory has many applications and interactions in computer science (trace languages of Mazurkiewicz, Petri nets and “Tetris models” by Maraisse and co-author, etc ...) in statistical mechanics (directed model, hard gas model such as Baxter hard-hexagonal model, or q-Bessel appearing in the SOS model and paths with interactions, etc ..). They also appeared in 2D Lorentzian quantum gravity (work of Ambjorn, Loll, Di Francesco, Guitter, Kristjansen and Viennot with his Australian student W.James).

In the context of the O(1) loop model on a cylinder and the RS conjecture, one should consider heaps of dimer on a cycle and the action of adding a dimer on the O(1) loop. We believe that the model of heaps of dimers on a circle gives a slightly different point of view that the one followed by physicists in their description of the 0(1) loop model and action of the Temperley-Lieb algebra. The possible interest is that such heaps belong to a whole well developed theory. Remark that heaps of dimers on cycles has already been considered in the completely different context of the combinatorics of Strahler numbers with the so-called Kepler towers introduced by Viennot under the influence of D.Knuth.

Remark also that viewing Temperley-Lieb as heaps of dimers has also been recently developed by Green in a series of papers called “acyclic heaps of pieces”, with connection with the so-called fully commutative elements in a Coxeter group (Stembridge, 96). Green has given a classification of acyclic heaps of pieces, which again parallel the classical one with root systems (and cluster algebras).

3 - Combinatorial theory of orthogonal polynomials.

As described in B1, orthogonal polynomials play a crucial role in some topics related to ASM enumeration. A refined counting is the one when taking care of the observable parameter “number of -1 in the matrix”. This gives a polynomial A(x) with A(0)= n! and A(1) = A_n. Explicit formulae has been given in the case of 2- and 3- enumeration, that is replacing x by 2 (resp. 3) in A(x). Physicists F.Colomo (Firenze) and A.G.Pronko (Saint-Petersburg's) expressed the value of A(x) for x= 1, 2, 3 in term of certain Hankel determinants related to respectively continuous Hahn, Meixner-Pollaczek and continuous dual Hahn polynomials.

In a completely different and independent work , Tamm and Gessel, Xin (Brandeis university) in recent papers, have considered certain Hankel determinants of matrices with coefficients related to ternary trees. The values gives rise to the number of ASM, and of some classes of PP under certain symmetries (PPS).

In our group, two members have developed complete combinatorial theory of orthogonal polynomials, continued fractions and Padé approximants. Lascoux theory is based on his view of symmetric functions as lambda-rings, operators on polynomials and divided difference operators “à la Newton”. This theory constitutes some chapters of his CBMS Lecture Notes “Symmetric functions and combinatorial operators on polynomials” (280 pages) , published by the AMS. Another theory, with a complementary point of view has been developed by Viennot and lead to a 210 p. Lecture Notes published by the LACIM, Montréal in 1983. The starting point was Flajolet’s theory interpreting continued fractions as weighted Dyck or Motzkin paths and a certain fundamental bijection between permutations and the so-called “Laguerre histories” due to Françon-Viennot (FV) in 1978. This theory leads to many developments,in particular in the interpretation of the moments of the five orthogonal polynomials which are also Sheffer polynomials (in the sense of G.C.Rota theory, characterized by their exponential generating functions), i.e. Hermite, Charlier, Laguerre, Meixner and Meixner-Pollaczek (with parameters). Then E.Roblet (student of Viennot) extended this theory to the general Padé approximants theory and some more general continued fractions (T-fractions, L-fractions and branching continued fractions).

Our third natural objective is :

Objective 3 - In the light of Lascoux, Viennot and Roblet’s combinatorial theory of orthogonal polynomials and Padé approximants, explain the above relation between 1-, 2- and 3- enumeration of ASM and the continuous Hahn, Meixner-Pollaczek, and continuous dual Hahn polynomials; explain combinatorially the relation between the Hankel determinants of Tamm, Gessel and Xin and the ASM and the PPS.

In his 1983 Lecture Notes, Viennot has given some combinatorial interpretations of such Hankel determinants whose coefficients are the moments of some orthogonal polynomials, and in the case of the five Sheffer classes of orthogonal polynomials, the value of the Hankel determinant can be obtained without any calculus in a pure combinatorial way with bijections “à la FV”. Using such combinatorics, the A(2) formula should be explained. The A(1) and A(3) enumeration involved some Hahn polynomials and combinatorial interpretations of moments of orthogonal polynomials has not yet gone so high in the Askey tableau classifying orthogonal polynomials. There are strong hope to get combinatorially the moments of such Hahn polynomials, since the coordinator, in collaboration with D.Stanton and M.Ismail (1987) get a “semi” bijective proof of the Askey-Wilson integral. This integral is the key in he understanding of the Askey-Wilson orthogonal polynomials. Such polynomials are at the top of Askey classification, from which all other classical families or orthogonal polynomials can be deduced.

In a paper at FPSAC’00 (Moscow) Viennot has shown how the classical (in numerical analysis) and so-called qd or quotient-difference algorithm, computing the coefficient of the development into S-fractions of a given power series (equivalent to compute Hankel determinants of moments) can be derived from two easy manipulation on Dyck paths and 2-colored Motzkin paths. Such considerations are at the basis of a paper by DeSainte-Catherine and Viennot (1985) giving some pure combinatorial proof for formulae counting some packed configurations of dimers on a pentagonal-hexagonal lattice, in bijection with some Young tableaux, or configurations of non-crossing Dyck paths, given by a Hankel determinant of Catalan number. At that time, the coordinator was thinking of explaining the formulae of the form determinant = product/product (interpreted by configuration of non-crossing paths) by using some kind of “qd-algorithm” related to other families of paths, and interpreting the above formula as a product of rational fractions, in the same way as the product of fractions appearing in the qd-algorithm applied to the Catalan numbers. At this stage an amusing remark is that in the case of two non-crossing Dyck paths, we recover the Schnyder trees of N.Bonichon, and more generally, configuration of k Dyck paths are also the so-called “watermelons” with an absorbing wall, considered in a more general setting by Guttmann, Krattenthaler and Viennot in the context of the “Vicious walkers” introduced by M.Fisher in his Boltzmann lecture at StatPhys (1983).

4 - Schur, Schubert, Grothendieck polynomials and ASM

Schubert and Grothendieck polynomials, indexed by permutations, have been introduced by A.Lascoux and M.P.Schützenberger, in relation with algebraic geometry, using some divided difference operators. These polynomials have positive integer coefficients. They play a central role in nowadays combinatorics and have become a classical field of study. Monographes have been written by I.Macdonald and in France by L.Manivel.

As shown in the work of Di Francesco and Zinn-Justin, these Schubert polynomials appear in the inhomogeneous model of crossing loops in physics. A.Lascoux has shown how the (more general) Grothendieck polynomials (and thus Schubert polynomials) can be generated from ASM with a suitable weight function. Another direction of studies is

Objective4 - Extend the study of the connection between Schubert and Grothendieck polynomials and ASM, RS coefficients and extended RS models or loop models with crossings.

In particular it would probably be useful to relate this connections with the geometric generation of the Schubert polynomials given by Fomin and Kiriloov, inspired from the Yang-Baxter relation. For the symmetric part of such Schubert polynomials, Fomin and Viennot have shown that in the case of polynomials indexed by permutations having no occurrence of decreasing subsequence of length 3 (enumerated by the Catalan numbers), this geometric construction can be interpreted as the superposition of two non-crossing configurations of paths related to the determinants of the Jacobi-Trudi and its dual for skew Schur functions. Such study is related to the nil-Temperley-Lieb algebra mentioned above.

5 - Random discrete structures, Markov chains and experimental combinatorics.

The study of Markov chains, or of random discrete structures, play an important role in the comprehension of the (strong) RS conjecture. As mentioned above, a member of the team, P.Duchon has given a slight extension of the RS conjecture in the form of a pure combinatorial conjecture, and with J.F.Marckert, made some progress in the resolution of this new conjecture.

Going further needs the help of experimental combinatorics. There is a long tradition of experimentations, both in Bordeaux and in Marne-la-Vallée. the software ACE, for the manipulation of symmetric functions and Schubert or Grothendieck polynomials has been developed by S.Vegneau under the direction of A.Lascoux. In Bordeaux, we have a tradition of more visual experimentation for bijections and listing of combinatorial objects. Some members of the combinatorics group have founded a new team of “visualization of informations”, in relation with bio-informatics. Our final objectives will be:

Objective 5 -Using all the preliminary progress described in objectives 1,2,3 and 4, find a combinatorial proof of Duchon’s version of the RS (strong) conjecture.

Maybe, with a new comprehension of the relation between ASM and TSSPP, we should be able to reach

Objective 6 -Find a bijection between ASM and TSCPP.