Résumé des recherches (document pdf, 5 pages, en français)

more detailed descriptions in the secondary website:  Researches

(secondary website in construction)

Summary of research results

Xavier Gérard Viennot

Research domains

I have been working in the following fields: enumerative, algebraic and bijective combinatorics in relation (and with applications) to computer science, molecular biology, theoretical physics, control theory and pure mathematics.

Presentation of my research domains

Enumerative combinatorics is the art of counting “finite structures” or “combinatorial objects” by giving explicit formulae, or explicit expressions for the corresponding “generating function”, or at least some equations involving these quantities.

Algebraic combinatorics is the art of relating algebraic structures and combinatorial structures. One can associate algebraic structures to combinatorial objects, as for example the Jones polynomial associated to a knot, or the chromatic and the Tutte polynomial associated to a graph. Conversely, combinatorial objects appear in the study of certain algebraic structures, as for example the classical Young tableaux in the representation theory of symmetric groups. Another example are the so-called Loday-Ronco or Connes-Kreimer Hopf algebras (related to renormalisation in physics) based on combinatorial manipulations of trees.

In bijective combinatorics, the purpose is to “explain” the various formulae or equations appearing in combinatorics with the explicit construction of bijections and correspondences between various classes of combinatorial objects. By working with “weighted objects” and “weight preserving bijections”, a whole universe of identities are accessible via combinatorics, involving identities coming from number theory, algebra and classical analysis (special functions, orthogonal polynomials, ...). Before constructing bijections, one has first to give “combinatorial interpretation”, i.e. to invent a class of weighted combinatorial objects such that the sum of the weights of all these objects will give the polynomial, series or function coming from other banches of pure or applied mathematics.

Related topics are the random generation of combinatorial objects (i.e. to construct efficient algorithms giving a random object of a given “size” with uniform probability), also analytic combinatorics (that is the asymptotic study for the number of objects of a given type). There are several relations between these combinatorics and other part of pure and applied mathematics (algebra, number theory, analysis, probability theory, control theory, ...) and some other fields such as theoretical physics (statistical mechanics, fractals, quantum gravity, ...), computer science (automata theory, analysis of algorithms, computer graphics, ...) and molecular biology. Since 30 years, I have been working in all these domains. I summarize some of my main researches. I have published  2 monographs and about 80 papers in various journals in mathematics, computer science and physics, with 37 different coauthors.

    survey paper about enumerative combinatorics: [85]

    lecture notes of classes: [5], [86]

Combinatorial algebra

    My thesis, under the supervision of M.P.Schützenberger (from the French Academy of Science) was about “factorisations of free monoids” and constructions of “basis and basic families” of free Lie algebra.

    books or monographs: [1], [2], [3]

    papers: [8],[9],[10],[11],[12],[13],[14], [16]

Combinatorial interpretations of classical numbers and of special functions

    I gave combinatorial studies of the classical Euler numbers (tangent and secant numbers), of Genocchi numbers, and gave combinatorial interpretations of the Jacobi elliptic functions. These studies are related to the combinatorial studies of permutations, increasing binary trees and to the combinatorial theory of differential equations (see below).

    papers:   [21], [22], [23], [26] (survey paper), [77]

Genocchi numbers appeared recently in the press, “Sud-Ouest”, November 2007 ...

Combinatorics of permutations

        Here are some enumerative  and bijective studies about permutations. Most studies are in relation with combinatorial interpretations of classical numbers, special functions, orthogonal polynomials or differentials equations. Other results include a proof a conjecture of Foata and Schützenberger about an equidistribution of permutations having a given up-down sequence, and a bijective proof of the formula for the number of Baxter permutations.

            see also the section about “alternative tableaux, permutations and PASEP”.

    papers: [15], [20], [21], [23], [24], [25], [26], [31], [40], [69], [89]

Partitions of integers and q-culculus

    papers: [44], [45], [46]

Combinatorial theory of orthogonal polynomials

In relation with Flajolet theory of analytic continued fractions, I gave a complete combinatorial theory of general (formal) orthogonal polynomials based on the combinatorics of weighted Motzkin paths. (monograph of 210 pages): orthogonality, moments, continued fractions (Jacobi and Stieljes), Hankel determinants, interpretation of linearization coefficients for Hermite, Laguerre and Tchebychef polynomials, combinatorial theory of Scheffer polynomials (Hermite, Laguerre, Charlier, Meixner I and II), extension of the theory to Padé approximants, T-continued fraction, q-Laguerre, .., combinatorial interpretation of the quotient-difference algorithm in numerical analysis. Interpretation of the Askey-Wilson integral and combinatorial proof using interpretation of q-Hermite polynomials.

    see also the section below about “alternative tableaux, permutations and PASEP”.

    papers: [21], [32],[34], [45], [62], [69], [71], [72], [76]

Combinatorial theory of differential equations and control theory

With P.Leroux, we establish a combinatorial theory of general differential equations and integral calculus using some families of weighted and coloured increasing labeled trees. As a byproduct of the theory, we can interpret  combinatorialy and solve efficiently differential equations with forced terms, that is differential equations coming from control theory. The solution is given in term of expansions into Chen iterated integrals (equivalent to Volterra kernels) and we rederived Fliess approach with noncommutative formal power series. Using combinatorial algorithms relating trees and paths, we gave very efficient algorithms computing the coefficients of such series. Also using the combinatorics of such increasing trees, we can interpret some rational approximants of the general solution.

    paper: [43], [48], [49], [50], [63], [65], [66], [77]

Determinants and non-crossing configurations of paths

With Gessel, we gave a general methodology interpretating determinants  as certain configurations of non-crossing paths (subject to certain conditions). It was also introduced in terms of matroids by Lindström. This methodology applies to many examples of determinants appearing in various domains, not only in enumerative combinatorics, but also examples such as Hankel determinants in continued fractions theory (Jacobi and Stieljes), or the Jacobi-Trudi identity for Schur functions in the theory of symmetric functions.  We relate these configurations with the theory of Young tableaux and symmetric functions. This methodology has become very classical and has been applied in various situations in more than 100 papers. It is usually called the Lindström-Gessel-Viennot lemma (LGV lemma). The idea relating determinants and non-crossing of paths appear in many other contexts: the  theory of birth and death process by Karlin and McGregor, in physics with de Gennes and Fisher, also with John and Sachs, and in theoretical chemistry with Gronau, Just, Schade, Scheffer, Wojciechowski.

It is also related to the enumeration  of perfect matchings in graph (or paving lattices with dimers). It is classical in the combinatorial solution of the Ising model in statistical physics (Pfaffians) and also in theoretical chemistry. Another relation comes from modelisation of wet transitions in statistical physics as shown by Fischer with the so-called vicious walkers. With Guttmann and Krattenthaler, we solved some open problems in this direction (enumerating stars and watermelons in polymer lattice) relating configurations of non-crossing paths and related determinants with the theory of symplectic characters of the symmetric group.

    paper: [35], [51], [70], [73], [75], [79]

Young tableaux, symmetric functions and the RSK correspondence

The Robinson-Schensted-Knuth (RSK) correspondence is a very classical and well studied bijection between permutations and pairs of Young tableaux of the same shape. I gave a “geometric” version, with “light and shadows” of this famous correspondence. I introduced the concept of “good (i,j)-grids” in order to give a “local” definition of the correspondence. As mentioned above with determinants and configurations of non-crossing paths, I worked in the related field of symmetric functions, plane partitions, Schur functions, etc ... relating also geometric constructions for Schubert and Schur functions with heaps of dimers (see below) and Temperley-Lieb algebra.

    see also the papers [89] and [90] related to sections below about “alternative tableaux, permutations and PASEP” and “alternating sign matrices”.

    papers: [15], [17], [30] (survey paper), [39]

Cartier-Foata commutation monoids and combinatorial theory of heaps of pieces

Cartier and Foata introduced some monoids defined by generators and some partial commutations relations. These monoids are also called trace monoids. They were introduced as model in computer science for concurrency access to data structures and parallelism. I have interpretated the equivalence classes of words up to these commutations of letters (i.e. traces), by some combinatorial structures called heaps of pieces. These objects correspond to the intuitive idea of puting some pieces one over another, such as puting dimers on a chessboard. I have developed a general theory, with some basic lemma about generating functions, paths and heaps, etc. This theory applies to many situations going from the combinatorial of general orthogonal polynomials, algebraic graph theory (matching and chromatic polynomials), Rogers-Ramanujan identities, interpretation of ratio of q-Bessel functions, the Temperley-Lieb algebra, and most of all in statistical physics and in Lorentzian quantum gravity.

    paper:  [41], [44], [67], video of a survey talk at the Newton Institute, April 2007.

Statistical physics

I already mention my work about vicious walkers. Using our combinatorial theory of heaps of pieces, I have solved various conjectures about the so-called directed animal model, introduced by physicists in relation with directed percolation. I showed combinatorially the relation with some gas model and gave a combinatorial interpretation of the density of such gas model in term of certain heaps called pyramids. A famous and classical example is the hard hexagons model of Baxter. With Bousquet-Mélou, we used heaps theory for solving some polygons models with q-Bessel functions. The same combinatorics can be used to explain some formulae about the exact solution of some SOS (solid-on-solid) models or some polymers model with interactions, involving the same q-Bessel functions.

    We also have given a bijective study of the TASEP (totally asymmetric exclusion process) and PASEP (see below).

    paper: [37], [47], [73], [75], [81], [88], [89]

2D Lorentzian quantum gravity

Physicists introduced some finite combinatorial objects called dynamical Lorentzian triangulations. This is the “quantum geometry” approach to quantum gravity. In 2D dimension some models can be solved exactly. The explicit expression for the “path propagator from one geometry to another” can be understood using the theory of heaps of dimers on the positive integers. Lorentzian triangulations are in fact in bijection with certain heaps of dimers. With W. James, we explain bijectively some exactly solved model of Ambjorn, Loll, Di Francesco, Guitter, Kristjansen. Also, I gave a bijective proof for the generating function of 2D general Lorentzian triangulations (i.e. without borders conditions), which was given equivalently by Bousquet-Melou and Rechnitzer in terms of multidirected animals.

    papers: [78], [84]

Algebraic graph theory

      Some studies about the Tutte polynomial of a graph. Relation between the theory of heaps of pieces and chromatic polynomials of graph.

    paper: [38], [41]

Polyominoes enumeration

Equivalently to the notion of animal in physics, is the notion of polyomino. I solved the enumeration problem for various classes of polyominoes, in particular the convex polyominoes with Delest.

    papers: [27], [29], [36], [47], [61], [67], [68]

Computer science: automata, data structures and analysis of algorithms

I have worked in various domains of computer science, mainly in automata theory, then about algorithms, analysis of algorithms and data structures, and also in computer graphics. For data structures, with Françon and Vuillemin, we introduced the “pagoda structure” as an efficient way to represent the so-called priority queues. The underlying combinatorics involved for computing the mean cost of the algorithms is related to binary search trees, and I discovered recently that it is exactly the same as the combinatorics involved in the Hopf algebra of binary trees introduced by Loday and Ronco. In this direction I defined a “jeu de taquin” for binary trees and “sylvester monoid” analog to the famous one for Young tableauxand plactic monoid.

    papers: [6], [7], [15], [18], [19], [36], [57]

Computer graphics: synthetic images of trees

With Arquès, Eyrolles and Janin, we have given some algorithms for producing synthetic images of trees, leaves and landscapes. The methodology is based on the Horton-Strahler analysis of binary trees. This methodology has been first introduced in hydrogeology for the morphologic study of river networks. Then Horton-Strahler parameter reappeared in theoretical computer science as the minimum number of registers needed to compute an arithmetic expression. We made a refinement of this analysis by introducing the so-called “ramification matrix” for every tree-like structure. This is the basis for our work for producing synthetic images of trees and landscapes. The combinatorics of Horton-Strahler analysis is very rich and leads to deep results related to number theory, combinatorics and  orthogonal polynomials.

papers: [52], [55], [56], [58], [59], [60], [64]

Strahler distribution

    papers: [58] and [60] (survey papers), [74], [83], [80]

Analysis of fractals images in physics

With Vannimenus, we used the notion of ramification matrix of branching structures (introduced above in computer graphics) for the analysis of some fractal structures coming from physics such as the DLA model (“diffusion limited aggregation”) or “viscous fingers”. I mention that recently the notion of  ramification matrix has been used in radiology for the classification of galactograms with digital mammography.

    papers: [53]

Molecular biology

With Vauchaussade de Chaumont, we solved some problem posed by Waterman about secondary structures of molecules such as RNA. The problem involved  to the so-called parameter “complexity” of the molecule, introduced for the computation of the energy of the molecule in order for predicting the secondary structure knowing the primary structure. We show that some generating functions involve a parameter having the same distribution as the Horton-Strahler parameter (see above) for binary trees.

    paper: [28], [33]

History of mathematics

   In relation with the celebration of the 300th anniversary of the birth of Leonhard Euler and I made some studies about Euler and combinatorics.

    paper: [87]

Alternative tableaux, permutations and PASEP

    We introduce a new combinatorial object called "alternative tableau". This notion is at the heart of different topics: the combinatorics of permutations and of orthogonal polynomials, and in physics the model PASEP (partially asymmetric exclusion process).

    The model PASEP have been recently intensively studied by combinatorists, in particular giving combinatorial interpretations of the stationary distribution (works of  Brak, Corteel, Essam, Parvianinen, Rechnitzer, Williams, Duchi, Schaeffer, Viennot, ...). Some interpretations are in term of the so-called "permutation tableaux", introduced by Postnikov, followed by Steingrimsson and Williams, in relation with some considerations in algebraic geometry (total positivity on the Grassmannian).

    Permutations tableaux have been studied by Postnikov, Steingrimsson, Williams, Burstein, Corteel, Nadeau and various bijections with permutations have been given. The advantage of introducing alternative tableaux is to give a complete symmetric role for rows and columns. We give a bijection between the two kinds of tableaux and a direct bijection between permutations and alternative tableaux, called the “exchange-deletion” algorithm. We also give combinatorial interpretation of the stationary distribution of the PASEP in term of alternative tableaux. Particular case include Genocchi numbers and the combinatorics of binary trees and Catalan numbers (TASEP, totally asymmetric exclusion process).

    Then we show the relation between alternative tableaux and the combinatorial theory of orthogonal polynomials developed by Flajolet and the author. In particular the Françon-Viennot bijection between permutations and "Laguerre histories" (i.e. some weighted Motzkin paths) plays a central role here and enable us to construct another bijection between permutations and alternative tableaux.

    This last bijection is in the same vein as the construction of the classical Robinson-Schensted-Knuth correspondence by "local rules" as originally defined by Fomin. The bijection can also be presented in analogy with Schützenberger "jeu de taquin". In fact, taking the inverse of the permutations, this last bijection is nothing but the above “exchange-deletion” algorithm.

    paper [88] (for the TASEP), papers are in preparation such as [89], see also the video of the talk 13 April 2008 at the Isaac Newton Institute.

Alternating sign matrices, cellular Ansatz and the MARS project

    I started a new approach to the subject of alternating sign matrices (ASM). Such objects have been introduced about 25 years ago, in relation with 3D partitions (plane partitions) and intensive studies have been made by combinatorists, in relation with the six- vertex model with "domain wall boundary conditions". More recently, the convergence of interests between physics and combinatorics have been strengthened with the Razumov-Stroganov conjecture relating certain eigenstates of physical models (Heisenberg XXZ spins chain model at special value of the anisotropy parameter or loops model on a semi-infinite cylinder) with the enumeration of ASM and of FPL (fully packed loops configurations, in bijection with ASM). This domain, especially around the Razumov-Stroganonv conjecture, focuses nowadays considerable attention among combinatorists and physicists. It is the subject of our ANR project MARS, 2006/2009 (Aleternating Sign MAtrices and the Razumov-Stroganov conjecture).

    I propose in [90] an algebraic approach to ASM and FPL with operators satisfying certain commutation relations. This approach has the same flavor as Fomin’s algebraic approach with “local rules” or “growth diagams”, to the classical Robinson-Schensted correspondence between permutations and pair of Young tableaux. It is also in the same vein of recent work I am doing about the PASEP (Partially asymmetric exclusion process) in physics and the new notion of alternating tableaux I introduced in [89]. More generally, we can extend this algebraic approach to all the others combinatorial objects related to ASM, i.e. plane partitions, non-crossing and osculating paths, tilings of square and triangular lattice, etc ... This is the “cellular Ansatz”, introduced and stated in [90], which propose more open problems and alternative routes in this hot subject than new proofs or new enumerative results.