XAVIER VIENNOT
  • PART I
    • abstract
    • contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • list of bijections
    • index
  • PART II
    • abstract
    • contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Some lectures related to the course
  • PART III
    • abstract
    • contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • references, comments and historical notes
  • PART IV
    • introduction
    • contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • references
  • Epilogue

The Art of Bijective Combinatorics    Part II

Commutations and heaps of pieces with interactions in physics, mathematics and computer science

 

The Institute of Mathematical Sciences, Chennai, India  (January-March 2017)

Ch 5  Heaps  and  algebraic  graph  theory

Ch 5a

16 February 2017

slides_Ch5a         (pdf  19  Mo)             video Ch5a

example of a tree-like path     slides  (2,5 Mo)

 

dedication to Jean-Pierre Muller 3   video  53’’

«en guise d’apéritif»  5    video  1’ 16’’

        neighbourly heap  7   video  1’ 57’’

        maximal neighbourly heap   8   video  8’ 47

        example of non-maximal neighbourly heap  9   video    9’ 21’’

        two-neighbourly heap   12  video  10’ 49’’

        Wildberger theorem 12-13   video  11‘ 13’‘     the proof of this theorem is   here

        the swallow for E_7  18  video  14’ 05’’

 

complements  19   video  15’ 15’’

        minuscule representations of simply-laced Lie algebras  22  video  16’ 30’’

                see also the related paper of Wildberger      here

        Richard Greene’s book  24  video  17’ 20’’

 

algebraic graph theory   27  18’ 19’‘   video 

        characteristic polynomial of a graph  29  video  19’ 10’’

        matching polynomial  30-32   video  19’ 36’’

        perfect matchings  33   video   19’ 58’’

        chromatic polynomial  34   video  20’ 29’’

        acyclic orientation of graphs  36-37  video  21’ 47’’

        spanning trees  38   video  22’ 12’’

chromatic polynomials and acyclic orientation of graphs  42   video  23’ 44’’

        Stanley’s theorem  43   video  24’ 43’’

        4 ideas  45   video  27’ 18’’

        multilinear heaps: definition   47   video  28’ 57’’

       bijection between multilinear heaps and acyclic orientations  48  video  30’ 21’’

        heap associated to a ordered coloring  49   video   32’ 17’’

        an example  50-53   video  33’ 09’’

        layer factorization of a heap  55   video  35’ 06’’

        colored layered heap  56   video  38’ 23’’

        covering heap  57  video   39’ 32’’

         expression of the chromatic polynomial  60  video  41’ 20’’ 

        multicoloring of a graph  61     video  43’ 01

        multicoloring of a graph:  an example  63       video  45‘ 04’‘

        multicoloring on Rajasthan wall:

                                pictures «beyond the walls» by J.P. Muller  65-68  video  45’ 46’’

        chromatic power series  70    video   48’ 24’’

        a crucial identity  74  video  53’ 39’’

        end of the proof  78   video  56’ 49’’

        exercises  79-81  video  57’ 47’’

        correction: p81, see  (1)  below

matching polynomial  82    video   1h  03’  29’’

        matching polynomial:  definition  85  video   1h  04’ 24’’

        reciprocal of the matching polynomial  87  video   1h 06’ 02’’

        main theorem about the zeros of the matching polynomials  89  video  1h 06’ 54’’

        tree-like paths: definition  90   video  1h 09’ 24’’

        example of a tree-like paths on the square lattice  91  video  1h  11’ 15’’

           the story of «Le petit Poucet» lost in the forest by his parents  (see the auxiliary set of slides)

        construction of a tree associated to a graph  94    video  1h 14’ 06’’

                            (solution of exercise3, p65, Ch3b)

        end of the proof  98

the end 99   1h 18’ 27’’

 

(1) the proposition of Greene and Zaslavsky  has been proved by Lass in 2001 using tools called «fonctions d’ensembles», with methodology closed to heaps (sorry Bodo to have forgotten !)    here is his beautiful paper

Ch 5b

20 February 2017

slides_Ch5b     (pdf   20 Mo)        video Ch5b

 

from  the previous lecture  3

        complements to the exercise  Ch5a,p 81   6

zeta function of a graph  7

        Euler identity for the Riemann zeta function  10

        the first definition of the Ihara zeta function for a graph  14

        tail and backtracking in  a path  14

        two Bass’s evaluation of the zeta function for a graph  16

        some references  17

        backtracking through the bijection  Khi : 2 counter-examples  19-20

the second bijection Psi  path --- pair  (eta, E)  21

        the oriented line graph  LG of a graph G  23

        trail  and  oriented loops  24

        description of the bijection  Psi  25-28

        an example with trail and oriented loop  29

        characterization of non backtracking paths through the bijection  Psi  30

        discussion on configurations of the Ising model and oriented loops  31

the second definition of the zeta function of a graph  32

        proof of the equivalence with the first definition  34-35

the third definition of the zeta function of a graph  36

        construction of an involution  phi   40-41

        the special case of loops, backtracking and tail at the origin  42-44

        what remain to be done to complete the proof  45-47

        another zeta function for graphs  52

spanning tree of a graph  53

        an example  55

        the Laplacian matrix of a graph  56

        the matrix tree theorem  57

        an example  58

        proof of the matrix tree theorem  59-61

        the involution  60

        after the action of the involution: a spanning tree  61

        the case of a general minor of the Laplacian matrix  63

        path and spanning tree  64

Wilson’s algorithm revisited with heaps of cycles  66

        a theorem of Propp and Wilson (independence of the order of the points)  74

        coding of the steps of the algorithm with a pair  (spanning tree, heaps of cycles)  74

        proof by Marchal  74-77

the end   80