Course  IMSc  Chennai, India

January-March 2017

Enumerative and algebraic combinatorics,

a bijective approach:

commutations and heaps of pieces

(with interactions in physics, mathematics and computer science)

  Monday and Thursday  14h-15h30 

welcome

to the X.V. bijective course 

2 January - 19 March  2017

The Institute of Mathematical Science

preface

To be completed

Abstract

A spectacular renaissance is appearing in combinatorial mathematics, in relation with other fields such as theoretical physics, probabilities theory, algebraic geometry, analysis of algorithms in computer science or molecular biology.   The bijective point of view replaces analytic proofs of identities by the construction of correspondences between classes of combinatorial objects. "Bijective tools" are emerging, putting some order in this very active domain. The subject of this course, "commutations and heaps of pieces", is one of this bijective tools. A wide variety of results comes from 3 fundamental lemma on heaps of pieces.

In 1969, Cartier and Foata introduced some monoids defined by generators and some partial commutations relations  ab=ba. These monoids were also introduced in computer  science under the name trace monoids as a model 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 terms of heaps of pieces makes it very versatile for applications. Many authors have made various interactions of heaps theory to combinatorics, algebra (representation theory of Lie algebra), classical analysis (continued fractions, orthogonal polynomials), graph theory, computer science and theoretical physics (statistical mechanics, quantum gravity, ...).

This course is the second part of the «X.V. bijective course». The first part was given in 2016 at IMSc, see the website here. This second course can be followed independently. There will be some overlaps (formal power series and generating functions; the Catalan garden) with the first course.

contents

1. -introduction to the combinatorial theory of heaps: commutation monoids, basic definitions about heaps, equivalence commutation monoids and heaps monoids, graphs, posets and linear extension of a poset
   

2. -reminding formal power series and generating functions
   

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

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

5. -heaps and algebraic graph theory: zeros of matching polynomials, acyclic orientations, chromatic polynomial
   

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

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

8. -fully commutative elements in Coxeter groups and Temperley-Lieb algebra
   

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

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

complementary topics

- zeta function on graph and number theory

1. -minuscule representations of Lie algebra with operators on heaps
   

2. -basis for free partially commutative Lie algebra
   

3. -Ising model revisited with heaps of pieces
   

4. -interactions with string theory in physics
   

5. -the SAT problem in computer science revisited with heaps (from D. Knuth)
   

6. -heaps in computer science: Petri nets, aynchronous automata and Zielonka theorem
   

last update: 16 March 2017

go to:

the IMSc 2016 bijective course website

courses  website

main Xavier Viennot  website