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