Course  IIT  Madras 

January-February 2015

Combinatorics and Physics

A website dedicated to this course  with complements and solutions of exercises  is also       here

Abstract

The interaction between combinatorics and theoretical physics started in the 60's with a combinatorial resolution of the Ising model  for ferromagnetism by means of  enumeration of dimers tilings on a planar lattice (the Pfaffian method). In recent years, this interaction has been very active and fruitful not only for statistical mechanics, but also to other parts of physics (quantum field theory, dynamical systems, ...). A new domain called "combinatorial physics" is emerging. At the same time, there is a spectacular renaissance of combinatorics, especially for enumerative, algebraic and bijective combinatorics, in interaction with computer science and other parts of pure and applied mathematics. New tools are appearing in combinatorics such as heaps of pieces, the LGV lemma or bijections between planar maps and some decorated trees, having fruitful applications both in mathematics and in physics.

Here is a list of topics for this course:

- introduction to enumerative and bijective combinatorics

- non-crossing paths, tilings, determinants and Young tableaux. The LGV Lemma.

- introduction to the theory of  heaps of pieces (interpreting partial commutation of variables) : the 3 basics lemma

- heaps of pieces and statistical mechanics: directed animals, gas models, q-Bessel functions in physics

- heaps of pieces and 2D Lorentzian quantum gravity

- combinatorics of the PASEP (partially asymmetric exclusion model in the physics of dynamical systems), relation with orthogonal polynomials

- alternating sign matrices, Fully packed loop model (FPL) and the (ex)-Razumov-Stroganov conjecture

No preliminary knowledge in physics is needed. This course can be followed by both physicists and mathematicians. 

Monday-Wednesday 3-4:30 pm

Ch 0     Overview of the course

              14  january 2015

part 1     slides         (pdf  11,7  Mo,  48 p.)

part 2     slides         (pdf  12,6 Mo,  40 p.)

part 3      slides         (pdf  18,4  Mo,  34 p.)

part 4     slides          (pdf  14,1  Mo,  39 p.)

part 5     slides          (pdf  14,8  Mo,  40 p.)

             

Ch 1     Introduction to enumerative combinatorics,

                    generating  functions

              19  January 2015     slides_Ch1a      (pdf  16,6  Mo,  74 p.)  (version 2)

binary trees, p.2

ordinary generating function   p.13

formal power series: formalization  p. 27

operations on combinatorial objects  p 39

operations on combinatorial objects: formalization  p.46

examples of operations on combinatorial objects: integer partitions, q-series  p.53

bijective combinatorics, example: Catalan numbers  p.65

bijective combinatorics, exercise :  multiplicative recurrence for Catalan numbers  p.73

            21  January 2015     slides_Ch1b    (pdf  12,4  Mo,    51p.)  (version 2)

generating functions in combinatorics and in statistical mechanics p.2

Dyck paths  p.7

from binary trees to Dyck paths p.13

exercise :  bijective proof of Touchard idendity p.17

the bijective paradigm  p.18

rational generating functions  p.32

                27  January 2015        slides_Ch1e         (pdf 10,7 Mo, 32p.)

             Summary of the complementary slides of Ch1

from binary tree to Dyck paths  p.2  (video)

from triangulations to binary trees p.4 (video)

algebricity:  directed animals p.8

algebricity:  planar maps  p.16

substitution in generating functions, the exemple of Strahler number of binary trees p.24

Chapter  2  Dimers, tilings, non-crossing paths and determinant

                 27  January 2015               slides_Ch2a              (pdf  11 Mo,  46p.) (version 2)

the LGV Lemma   p.2

a simple example  p.11

proof of the LGV Lemma  p15

binomial determinants p22

another example: Narayana numbers  p.39

                 28  January 2015               slides_Ch2b             (pdf    21,1 Mo,  82p.) (version 2)

formulae for binomial determinants  p.2

exercise: another formula for binomial determinants p.19

exercise: MacMahon - Narayana determinant  p.22

semi-standard Young tableaux, contents-hook lengths formula  p.26

plane partitions, MacMahon formula  p.33

paths for plane partition  p.38

tilings  p.52

tilings on triangular lattices  p.56

perfect matchings  p.64

Pfaffian methodology  p.74

                    2 February  2015         slides_Ch2c       (pdf  14,5 Mo,  67p.)

Aztec tilings  p.2

bijection Aztec tilings ----  non-intersecting paths  p.12

determination of the related Hankel determinant of Schröder numbers  p.25

                      (bijectively, new proof )

Hankel determinants and continued fractions  p.36

Weighted Motzkin paths  p.38

Expression of the coefficients in the continued fraction with Hankel determinants  p.46

A last example  p64

Chapter 3  Heaps of pieces

                        4 February 2015    slides_Ch3a        (pdf, 21,6 Mo,  90p.)

                        9  February 2015       slides_Ch3b             (pdf,  22 Mo,  93p.)

     

Chapter 4    Heaps of pieces  in  physics                

                         11  February 2015     slides_Ch4a          (pdf, 24,4 Mo,   71p.) 

                         16  February 2015     slides_Ch4b         (pdf, 15,8 Mo,    57p.)

Chapter 5  Combinatorics  for  the  PASEP

                        19  February 2015            slides_Ch5a            (pdf, 13,7 Mo,   78p.)

          

                        19/23 February  2015      slides_Ch5b             (pdf,  14,8 Mo,  63p.)       

                        23 February  2015             slides_Ch5c               (pdf, 7,9Mo,  56p.)

Chapter 6  PASEP  and combinatorics of orthogonal polynomials

                       25 February  2015     slides_Ch6a        (pdf, 19,6 Mo,   66p.)

                       25 February  2015     slides_Ch6b       (pdf,  16,6 Mo,   71p.)

                         2  March  2015         slides_Ch6c              (pdf, 19,5 Mo, 100p.)

Chapter 7  The cellular  ansatz

for a reminding of the RSK correspondence see Ch7a and Ch7b in the complementary website dedicated to this course  here

                         4 March  2015             slides_Ch7c   (pdf, 15,4 Mo,  106p.)

                               From a representation of the algebra  UD=DU+Id to the RSK correspondence

                          4 March  2015           slides_Ch7d    (pdf, 10,7 Mo,  43p.)

                                From a representation of the PASEP algebra  DE=ED+E+D

                         to a bijection   alternating tableaux -- Laguerre histories  (permutations)

                          9 March 2015           slides_Ch7e    (pdf,  9 Mo,  39p.)

                                 The general theory: Q-tableaux

                           9 March 2015          slides_Ch7f    (pdf,  25 Mo,  114p.)

                                 The XYZ algebra and its Q-tableaux

A website dedicated to this course  with complements and solutions of exercises  is also       here