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)
Contents
Chapter 1 Commutation monoids and heaps of pieces: basic definitions
Ch 1a Commutation, heaps of pieces, heaps monoids, equivalence commutation and heaps monoids,
Ch 1b Cartier normal form, lexicographic (Knuth) normal form, semi-pyramids (of dimers), heaps, posets and linear extensions,
Ch 1c Equivalence heaps and heaps of subsets, 2nd (original) definition of heaps (over a graph), heaps of dimers and symmatric group
Chapter 2 Generating function of heaps of pieces
Ch 2a The algebra of formal power series, operations on combinatorial objects, Dyck paths, algebraic equation for pyramids of dimers,
bijection Dyck paths -- semi-pyramids of dimers,
Ch 2b Inversion Lemma 1/D, extension N/D, Fibonacci, Lucas and Tchebychef polynomials,
Ch 2c Matching polynomial of a graph, second proof of N/D, Lazard elimination, Möbius function in monoids and posets,
Ch 2d The logarithmic lemma, second proof with exponential generating function, general form with species of heaps of F-structures
Chapter 3 Heaps and paths, flows and rearrangement monoids
Ch 3a The flow monoid, paths and flow monoid, rearrangement and heaps of cycles, the third basic lemma: the bijection paths -- heaps,
Ch 3b the bijection χ between paths and heaps, loop-erased process (LERW), example with Dyck paths, tree-like paths, spanning tree of a graph,
Wilson's algorithm for random spannning tree
Chapter 4 Linear algebra revisited with heaps of pieces
Ch 4a Inversion of a matrix, MacMahon Master theorem, Brauer identity for LERW,
Ch 4b Jacobi identity, 2nd proof with exponential generating function, β-extension of MacMahon Master theorem, Cayley-Hamilton theorem,
Ch 4c Jacobi dual identity, extension of LGV Lemma with heaps, relation with Fomin's theorem on LERW
Chapter 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,
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
Chapter 6 Heaps and Coxeter groups
Ch 6a the heap monoid of a Coxeter group, reduced decomposition, heaps and fully commutative elements of Coxeter groups, stair decomposition of a heap of dimers,
fully commutative heaps of dimers, relation with parallelogram polyominoes, bijection FC elements -- (321)-avoiding permutations,
Ch 6b the Temperley-Lieg algebra, complement: relation with symmetric functions, (321)-avoiding permutations, Jacobi-Trudi identity
Chapter 7 Heaps and statistical mechanics
Ch 7a Ising model, gas model, directed animals and heaps of dimers, the formula 3^n, themodynamic limit, hard hexagons gas model,
Ch 7b Lorenztian triangulation in 2D quantum gravity, the curvature parameter of the 2D space-time, connected heaps of dimers, the nordic decomposition,
Ch 7c q-Bessel function in physics
parallelogram polyominoes and q-Bessel, other description of the bijection parallelogram polyominoes -- semi-pyramids of segments, q-Bessel and SOS model,
Ramanujan continued fraction and heaps of dimers
Kepler towers
The playlist from matsciencechannel of the 19 videos of this course is here
complementary topics
- zeta function on graph and number theory
-minuscule representations of Lie algebra with operators on heaps
-basis for free partially commutative Lie algebra
-Ising model revisited with heaps of pieces
-interactions with string theory in physics
-the SAT problem in computer science revisited with heaps (from D. Knuth)
-heaps in computer science: Petri nets, aynchronous automata and Zielonka theorem