Course  X.V.  IMSc 2017

 
 





Ch5  Heaps  and  algebraic  graph  theory


    For each item, the first number refers to the page of the slides, clicking on «video» takes you directly to the corresponding slide in the video.  (Ch5b  to be completed)


Ch5a

                     16 February 2017

                                   slides_Ch5a         (pdf  19  Mo)             video Ch 5

                    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



Ch5b

                     20 February 2017

                                slides_Ch5b     (pdf   20 Mo)        video


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

       






go to:

the IMSc 2016 bijective course website

courses  website

main Xavier Viennot  website