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