Exposé CIRM, Luminy, 25 June 2021
Lattice paths and heaps
colloque Lattice paths, combinatorics and interactions
Marches aléatoires, combinatoire et interactions
CIRM, Luminy, 25 June 2021
slides (pdf, 45 Mo)
augmented set of slides with the original slides of the video
+ some slides (in blue background) with references and comments on the questions at the end of the talk.
CIRM video (CIRM version)
Vimeo version
abstract:
Recently several papers appears on ArXiv, on various topics apparently unrelated such as: spin system observable (T. Helmuth, A. Shapira), Fibonacci polynomials (A. Garsia, G. Ganzberger), fully commutative elements in Coxeter groups (E. Bagno, R. Biagioli, F. Jouhet, Y. Roichman), reciprocity theorem for bounded Dyck paths (J. Cigler, C. Krattenthaler), uniform random spanning tree in graphs (L. Fredes, J.-F. Marckert). In each of these papers the theory of heaps of pieces plays a central role.
We propose a walk relating these topics, starting from the well-known loop erased random walk model (LERW), going around the classical bijection between lattice paths and heaps of cycles, and a second less known bijection due to T. Helmuth between lattice paths and heaps of oriented loops, in relation with the Ising model in physics, totally non-backtracking paths and zeta function in graphs.
For Dyck paths, these two bijections involve heaps of dimers and heaps of segments. A duality between these two kinds of heaps appears in some of the above papers, in relation with orthogonal polynomials and fully commutative elements. If time allows we will finish this excursion with the correspondence between heaps of segments, staircase polygons and q-Bessel functions.
Description of the conference in details, with the page number of the slides and corresponding links sending directly in the video
(The video is the YouTube version)
Lattice paths and heaps
lattice, paths, heaps 2
intuitive definition of heaps with dimers 4 0:48
heaps of hexagons 6 1:50
7 papers using heaps 8-9 2:25
Reciprocity 11 4:32
alternating sequence:definition 14 7:37
Hankel determinants 15 8:11
bounded paths D_2n (k) 19 10:09
Generating function for bounded Dyck paths
first basic Lemma:the bijectin paths -- heaps of cycles 21 10:51
LERW loop erased random walk 22 11:06
The first fundamental Lemma on heaps:
The bijection paths -- heaps 31 12:39
(idea of) a heap of cycles 36 15:02
maximal piece of a heap: definition 39 16:54
random spanning tree, Wilson algorithm, Aldous-Broder algorithm 45 19:36
Example with Dyck paths 47 20:12
the bijection paths of D_2n^(k) and heaps of dimers on a segment 49 20:42
the bijection Dyck paths -- semi-pyramids of dimers 69 22:29
semi-pyramids of dimers: definition 23:50
Bijection alternating sequences -- heaps of segments (even case) 76 24:24
Bijection alternating sequences -- heaps of segments (odd case) 87 28:34
Second basic lemma on heaps:
the inversion Lemma 1/D 99 30:47
examples: heaps of dimers on a segment 107 32:03
Fibonacci polynomials 110 32:18
reciprocity 111 32:47
reciprocity heaps of segments -- heaps of dimers (even case) 114 33:26
Fibonacci and Tchebychev polynomials 118 34:57
reciprocity pyramids of segments -- semi-pyramids of dimers (odd case) 121 35:20
Reciprocity (odd case), Extension of the inversion Lemma N/D 122 35:22
Tip of the iceberg 129 37:21
Andrews theorem about the "reciprocal"of the Ramanujan continued fraction 141 39:40
quasi-partitions: definition 142 39:51
Some history 152 41:57
Delannoy and Rouché 156 43:48
Arbogast tableau for Catalan and ballot numbers 161 46:36
Heaps of pieces and commutations 165 48:34
Fully commutative elements in Coxeter groups 181 51:28
fully commutative element in a Coxeter group: definition 186 52:56
the duality heaps of segments -- heaps of dimers in the context
of fully commutative elements in the symmetric group 191 54:01
The duality heaps of segments -- heaps of dimers in the context
of the first and second bijection paths -- heaps 222 57:26
Helmuth approach for the Ising model 224 57:42
non-backgtracking paths 225 57:51
second bijection between paths and heaps (trail and oriented loops) 226 57:54
The third fundamental Lemma on heaps:
the logarithmic Lemma 230 58:17
Zeta function of a graph 232 58:26
Bijection Dyck paths -- heaps of oriented loops 237 59:08
A festival of bijections 254 59:14
staircase polygons (= parallelogram polyominoes), heaps of segments and q-Bessel functions 263
The "video-book" "The Art of Bijective Combinatorics", Part II, Commutations and heaps of pieces 266
The end Thank you! 267 59:43
Answers to questions
first question of Bishal Deb about Hankel determinants 1:00:02
D. Zeilberger question (paths and ballot numbers in Arbogast'book) 268 1:01:22
in response about P. Di Francesco question 269 (q-parameter in heaps of pieces) 1:03:21
in addition to the link given by C. Banderier 271 (the LGV Lemma)
in response to the question of P. Biane 273 (reciprocity for Rieman zeta function) 1:06:52
in response to the question of Joones Turunen 274 (quantum gravity) 1:08:48
in response to the second question of Bishal Deb 275 1:11:25
From the home page for mathematics of IMSc (The Institute of Mathematical Science, Chennai, India):
bijective proof of the Giambelli identity with lattice paths and LGV Lemma 276
Thank you ! 277 1:12:59
The End 1:13:18
Thank You ! Merci Infiniment !