• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • 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
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • 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
    • Lectures related to the course
  • PART III
    • Preface
    • 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
    • Preface
    • 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   Wildberger's theorem (for simply-laced Lie algebra), chromatic polynomial and acyclic orientations of graphs (Stanley's theorem),
chromatic power series and multilinear heaps over a graph, zeros of mathcing polynomials and tree-like paths

16 February 2017
slides_Ch5a         (pdf  19  Mo)            
example of a tree-like path     slides  (2,5 Mo)
video Ch5a  link to Youtube
video Ch5a  link to bilibili
dedication to Jean-Pierre Muller   3   0:54
«en guise d’apéritif»   5    1:16
        neighbourly heap  7   1:57
        maximal neighbourly heap   8     8:47
        example of non-maximal neighbourly heap  9    9:21
        two-neighbourly heap   12   10:49
        Wildberger theorem 12-13    11:13     the proof of this theorem is   here
        the swallow for E_7  18   14:05
complements  19   15:15
        minuscule representations of simply-laced Lie algebras  22   16:32
                see also the related paper of Wildberger      here
        Richard Greene’s book  24   17:20
algebraic graph theory   27   18:19
        characteristic polynomial of a graph  29    19:10
        matching polynomial  30-32    19:36
        perfect matchings  33     19:58
        chromatic polynomial  34    20:29
        acyclic orientation of graphs  36-37    21:48
        spanning trees  38     22:12
chromatic polynomials and acyclic orientation of graphs  42    23:45
        Stanley’s theorem  43    24:43
        Four ideas  45   27:18
        multilinear heaps: definition   47    28:55
       bijection between multilinear heaps and acyclic orientations   48    30:22
        heap associated to a ordered coloring   49     32:17
        an example   50-53    33:09
A theorem of Stanley giving another definition of the chromatic polynomial   54    34:03
        layer factorization of a heap   55    35:06
        colored layered heap   56     38:24
        covering heap   57   39:33
        expression of the chromatic polynomial with multilinear heaps over the graph  60    41:21
        multicoloring of a graph   61     43: 02
        multicoloring of a graph:  an example   63    45:04
        multicoloring on Rajasthan wall:
                                pictures «beyond the walls» by J.P. Muller  65-68     45:47
        chromatic power series   70      48:25
        a crucial identity   74     53:39
        end of the proof   78     56:49
        exercises   79-81    57:48
        correction:  p81, see  (1)  below 
matching polynomial  82       1:03:28
matching of a graph   84     1:04:12
        matching polynomial:  definition  85    1:04:26
        reciprocal of the matching polynomial  87    1:06:02
        main theorem about the zeros of the matching polynomials  89    1:06:56
        tree-like paths: definition  90    1:09:26
        example of a tree-like paths on the square lattice  91    1:11:16
           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     1:14:06
                            (solution of exercise3, p65, Ch3b)
        end of the proof  98
the end 99   1: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   zeta function of a graph, non-batracking paths, second bijection  ψ  between paths and heaps of loops, spanning tree of a graph,
matrix-tree theorem, Wilson's algorithm revisited with heaps of cycles

20 February 2017
slides_Ch5b     (pdf   20 Mo)        
video Ch5b  link to Youtube
video Ch5b  link to bilibili
from  the previous lecture  3    0:10
        complements to the exercise  Ch5a,p 81   6    1:56
zeta function of a graph  7     3:46
        Euler identity for the Riemann zeta function  10    5:40
some definitions: circuit, prime circuit, equivalence class of a circuit   12    8:27
        the first definition of the Ihara zeta function for a graph  14    12:43
        tail and backtracking in  a path  14    13:31
discussion with Amri: comparison between this definition of zeta function for a graph and the classical Riemann zeta function in number theory     15:23
        two Bass’s evaluation of the zeta function for a graph  15    18:50
        some references  16    21:20
expression for the logarithmic derivative of the first definition of Ihara zeta function fro a graph   17    23:38
discussion about the correctness of slide 17     25:25
        backtracking through the bijection  Khi : 2 counter-examples  19-20    31:02
the second bijection Psi  path --- pair  (eta, F)  21    33:51
        the oriented line graph  LG of a graph G  23    35:10
        the second bijection: trails  and  oriented loops  24    36:40
an example with trail and oriented loop  29    39:29
        description of the bijection  Psi  22-28    42:27
        an example  of the bijection  Psi  29    46:22
        characterization of non backtracking paths through the bijection  Psi  30    46:52
        discussion on configurations of the Ising model and oriented loops  31    48:07
the second definition of the zeta function of a graph  32    49:53
        proof of the equivalence with the first definition  34-35    51:10
the third definition of the zeta function of a graph  36    53:36
        construction of an involution  phi   40-41    56:54
        the special case of loops, backtracking and tail at the origin  42-44    1:01:15
        what remain to be done to complete the proof  45-47    1:04:19
another zeta function for graphs: deleting the no backtracking condition   46    1:06:15
discussion: going back to the source of bijective proofs    1:08:46
spanning tree of a graph  53    1:10:50
        an example  55    1:11:13
        the Laplacian matrix of a graph  56    1:11:23
        an example  58    1:12:12
 the matrix tree theorem  57    1:13:20
        proof of the matrix tree theorem  59-61    1:13:53
        the involution  61    1:15:10
        after the action of the involution: a spanning tree  62  (slide added after the video)
        the case of a general minor of the Laplacian matrix  63    1:19:02
        path and spanning tree  64    1:19:30
Wilson’s algorithm revisited with heaps of cycles  66    1:21:21
        a theorem of Propp and Wilson (independence of the order of the points) 
        coding of the steps of the algorithm with a pair  (spanning tree, heaps of cycles)  74    1:21:53
        proof by Marchal  74-77    1:22:07
the end   80    1:25:03