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 4 Linear algebra revisited with heaps of pieces
Ch 4a Inversion of a matrix, MacMahon Master theorem, Brauer identity for LERW
6 February 2017
slides_Ch4a (pdf 12 Mo)
video Ch4a link to YouTube
video Ch4a link to bilibili
Inversion of a matrix 4 2:08
recalling the classical formula for the inverse matrix with cofactor and determinant 5 2:16
replacing B by I-A 6 3:22
elementary lemma: paths and inversion of (I-A) 7 4:16
recalling the bijection khi between paths and heaps 8-9 6:42
applying the inversion lemma 10-11 9:02
proposition: expression of the generating function for weighted paths as the ratio N_i,j / D 12 11:33
elementary exercise: expressing the determinant of (I-A) 13 12:18
expressing the cofactor (i,j) of the numerator 14 15:26
end of the proof of the main proposition 15 17:12
discussion about this proof 17:34
Examples 16 26:24
transition matrix methodology in physics 17 26:31
bounded Dyck paths 18 27:25
generating function for bounded Dyck paths 19-20 27:57
discussion 29:35
reminding the Fibonacci polynomials 21 37:25
semi-pyramids of dimers on a segment 22 37:55
generating function for Fibonacci polynomials 23-24 38:10
exercise: directed paths on the square lattice 25-26 47:11
MacMahon Master theorem 27 50:54
inversion lemma: heaps of cycles 31 52:13
heaps of cycles and rearrangements 38 53:00
MacMahon formulation 40-41 54:19
relation with quivers and gauge theory in physics 42 1:01:02
Complements: an identity of Bauer for loop-erased random walks 43 1:03:14
Bauer's identity 46 1:05:40
proof of Bauer's identity 47-52 1:09:09
research problem: substitution in heaps 53 1:14:52
the end 54 1:17:16
Ch 4b Jacobi identity, 2nd proof with exponential generating function, β-extension of MacMahon Master theorem, Cayley-Hamilton theorem
9 February 2017
slides_Ch4b (pdf 19 Mo)
video Ch4b link to YouTube
video Ch4b link to bilbili
Correction to exercise 3, p65, Ch3b 3 0:09
From the previous lecture 4 2:17
From Ch2d: the logarithmic lemma 10 4:38
a paradox ? 16 8:33
Proof of Jacobi identity 17 11:04
Jacobi identity with exponential generating function 25 19:26
condition (m) for an assemblée of labeled pyramids 31 26:19
going back to Part I, Ch3a with the example of a permutation (in cycle notation) 36:10
discussion on species, labeled pyramids and exponential generating functions 38:25
end of discussion and end of the proof of Jacobi identity 42:04
Beta extension of MacMahon Master theorem 35 44:42
Cayley-Hamilton theorem 42 49:05
another weight preserving involution 53 1:05:03
Complement and exercise: a general transfer theorem 57 1:07:40
exercise 62 1:14:44
Next lecture: Jacobi duality 63 1:16:25
The end 65 1:17:42
Ch 4c Jacobi dual identity, extension of LGV Lemma with heaps, relation with Fomin's theorem on LERW
13 February
slides_Ch4c (pdf 23 Mo)
video Ch4c link to YouTube
video Ch4c link to bilibili
Jacobi duality 4 0:48
the classical relation between the minors of a matrix and the minors of its inverse 5 0:56
the main theorem 6 2:14
applying the inversion lemma from the main theorem 7-8 9:03
special case 1: I and J have only one element 9 10:53
deducing Jacobi identity from the main theorem 13-17 12:52
a Lemma expressing minors 14 13:29
end of the combinatorial proof of Jacobi duality 17 17:20
an example 18 17:32
Special case 2: no cycles 23 20:26
The LGV Lemma (from the course IMSc 2016, Ch5a) 25 21:07
the crossing condition 30 23:08
the LGV Lemma with the crossing condition 31 24:08
A simple example 34 25:24
Another example: binomial determinants 38 26:50
Proof of the LGV Lemma 48 30:28
the LGV Lemma in its general form 54 33:52
Proof of the main theorem: introduction 55 34:32
Visualization of the main theorem 60-61 37:11
Visualiation of what must be done in order to prove the main theorem 62 38:06
how to handle this mixture of cycles, an idea coming from physics:
discussion for defining a simultaneous loop-erased process 38:34
the problem for defining the involution 64 40:50
Proof of the main theorem: first step with Fomin theorem 65 41:45
Fomin's theorem 67 42:42
Proof of the main theorem: second step 75 51:15
another proposition 76 51:26
end of the proof 78
other proof using Grassmann algebra and integral related fo physics (Carrozza, Krajewski, Tanasa) 79 58:38
another way to prove the Jacobi duality identity (Lalonde, Talaska) 80 59:07
Crossing condition 87 1:02:31
main theorem with crossing condition 89 1:02:46
a funny example with paths on the square lattice 91 1:03:55
The end (of the video) 92 1:10:44
About the terminology «LGV Lemma» 92 (not in the video)
The end 98
Corrections: