Cours  Universidad de Talca

  (December 2013 - January  2014)

Heaps  of  pieces (24 h)

(with interactions in mathematics and physics)

     

In relation with combinatorial and probabilistic properties of rearrangements of sequences,  Cartier and Foata introduced some monoids defined by generators and some partial commutations relations. These Cartier-Foata monoids are also called trace monoids. They were also introduced as model in computer science for concurrency access to data structures and parallelism. Heaps of pieces have been introduced by the speaker in 1985 as a geometric interpretation of such monoids. The spatial visualization of elements of the monoids in term of heaps makes it very versatile for applications. Since the introduction of heaps, many authors have made various contributions in applying the heaps point of view to combinatorics, algebra and theoretical physics. The course introduces the basic definitions and lemma, and show these various possible applications, especially in physics.

abstract of the course

1. -introduction to the combinatorial theory of heaps: basic definitions
   

2. -the 3 basic lemma: inversion formula and generating function for heaps, the logarithmic formula, equivalence between paths and heaps of cycles
   

3. -combinatorial proof with heaps of classical theorems in linear algebra, MacMahon master theorem
   

4. -heaps for a combinatorial theory of formal orthogonal polynomials and continued  fractions
   

5. -interpretation of the reciprocal of the Rogers-Ramanujan identities with heaps of dimers
   

6. -heaps and algebraic graph theory: zeros of matching polynomials, acyclic orientations
   

7. -applications to statistical physics: directed and multidirected animals, parallelogram polyominoes and Bessel functions, hard gas models, Baxter hard hexagons model, Ising model revisited
   

8. -application to 2D Lorentzian quantum gravity: causal triangulations
   

9. -fully commutative elements in Coxeter groups
   

some references

the two historical papers:

1. -X.G.Viennot, Heaps of pieces, I: Basic definitions and combinatorial lemma, in « Combinatoire énumérative », eds. G. Labelle et P. Leroux, , Lecture Notes in Maths. n° 1234, Springer-Verlag, Berlin, 1986, p. 321-325.       pdf
   

2. - X.G.Viennot, Problèmes combinatoires posés par la physique statistique, in Séminaire Nicolas BOURBAKI, exposé n°626, Astérisque n°121-122, Soc. Math. France, 1985, p. 225-246.      pdf
   

for an introduction see:

100. C.Krattenthaler, “The theory of heaps and the Cartier-Foata monoid",  appendice to the reedition of the monograph "Commutation and Rearrangements" by P.Cartier et D.Foata, SLC, 2006,  and the references within, 
     

  see the web page of   SLC  (Séminaire Lotharingien de Combinatoire)

another pictorial introduction with slides and video:

1. -X.G.Viennot, Introduction to the theory of pieces with applications to statistical mechanics and quantum gravity in workshop “Combinatorial Identities & their Applications in Statistical Mechanics”,  Isaac Newton Institute for Mathematical Science, Cambridge, 7 April 2008       slides       (pdf, 21 Mo)      video
   

  

other references:

-  A paper( in french) introducing enumerative, algebraic, bijective ... combinatorics from elementary to recent researches,    LMA3.Viennot.v4.pdf

“Enumérons ! (De la combinatoire énumérative classique aux nouvelles combinatoires : bijective, algébrique, expérimentale, quantique et … magique)”, article dans “Leçons de mathématiques d’aujourd’hui ”, vol 3,  éds. Eric Charpentier et Nicolas Nikolski,  Cassini, Paris, 2007, pp 165-238.

1. -A complete text  (in french) about generating functions in combinatorics (ordinary and exponential), covering Ch1 and Ch2 of the Talca course 2010/2011. (160p), see my first website at the page «cours», the lecture Notes 1988  «séries génératrices énumératives»
   

Ch1   Commutation  monoids and heaps of pieces:  basic definitions

            11 and 12 December  2013         slides      (pdf   20,1 Mo  )

Commutation monoids  (Cartier-Foata)

Heaps of pieces: definitions, examples

Heaps monoids

Equivalence heaps monoids -- commutations monoids

Posets, linear extensions and words

Heaps of dimers, symmetric group

    Ch1c   Other definitions of heaps  (complements)    slides     (pdf   9,2 Mo)

preparation for Ch2:

Ch2a   Ordinary generating functions

       18 December 2013  slides    (pdf  10,3 Mo)

Binary trees

Formal power series: example and formalisation

Operation on combinatorial objects: example with binary tree

Dyck paths, algebraic equation for semi-pyramid

Bijective combinatorics

Operation on combinatorial objects: example with partitions of integers

Operation on combinatorial objects: formalisation

Ch2   Heaps  generating functions

        19 December 2013    slides   (pdf  8,1 Mo)

Inversion Lemma  1/D

Moebius function  (complements)

Extension  N/D

Second proof of N/D

Lazard elimination  (complements)

Log of a heap

Second proof with exponential generating functions   (complements)

Ch3   Flows monoid, paths and rearrangements

        23 December 2013    slides   (pdf  6,9 Mo)

Definitions: flow, path, circuit, cycle, rearrangement

Path = heap of cycles + self avoinding walk

Rearrangement = heap of cycles

Ch4  Heaps and linear algebra: bijective proof of classical theorems

              7 January 2014      slides  (pdf   5,8 Mo)

Inversion of a matrix with cofactors and determinant

Example: bounded Dyck paths and Tchebychef polynomials

MacMahon  Master theorem

Cayley-Hamilton theorem

A general transfert theorem  (complements)

Jacobi identity  (complements)

Jacobi duality  (complements)

Ch5  Heaps  and  combinatorial theory of orthogonal polynomials

          8 January 2014    slides    (pdf    7,2 Mo)

Examples:Tchebychef and Hermite polynomials

(formal) Orthogonal polynomials: definition, pavages and 3-terms linear recurrence relation

Bijective proof of Favard theorem, interpretation of the moments  with semi-pyramids

Examples of moments, the Askey tableau, classical orthogonal polynomials

Moments and weigthed Motzkin paths

Tridiagonal matrices

Ramanujan algorithm for computing the coefficients lambda(k) knowing the moments  mu(n)  (complements)

Ch5b  Heaps  and  combinatorial  theory of  continued  fractions

         10 January 2014      slides    (pdf  11,9  Mo)

Arithmetic continued fractions

Analytic continued fraction: an example with Catalan numbers

Another example with the Ramanujan continued fraction

Analytic continued fraction: Jacobi (J-fraction) and Stieljes (S-fraction) continued fraction

Convergents of a continued J-fraction

Continued fraction in terms of weitghted paths (Motzkin and Dyck)

Back to Ramanujan continued fraction

Bijective proof of Andrews theorem about the reciprocal of Ramanujan continued fraction

Ch6  Heaps  and algebraic graph theory

        14 January 2014      slides    (pdf  8,3  Mo)    (temporary  version)

Ch7   Heaps  in statistical  physics: directed animal and gas models

           15 January 2014      slides    (pdf  8,9  Mo)    (temporary  version)

Ch7b  Heaps in 2D quantum gravity: Lorentzian triangulations

            16 January 2014      slides    (pdf  7,3  Mo)    (temporary  version)

Ch8   Heaps and  q-Bessel functions in statistical physics:

    parallelogram polyominoes and SOS model

         21  January 2014      slides    (pdf  4,6  Mo)    (temporary  version)

Ch9  Heaps  and  fully commutative class of words in Coxeter groups

         22  January 2014      slides    (pdf   8,5 Mo)    (temporary version)

Epilogue:   Kepler  towers

         23  January 2014      slides   (pdf   5,0 Mo)   (temporary  version)