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:
