What (if anything) happened to Viennot's theory of Heaps of pieces? - MathOverflow

What (if anything) happened to Viennot's theory of Heaps of pieces?

2010-03-12T04:22:12Z

In 1986 G.X. Viennot published "Heaps of pieces, I : Basic definitions and combinatorial lemmas" where he developed the theory of heaps of pieces, from the abstract: a geometric interpretation of Cartier-Foata's commutation monoid. This theory unifies and simplifies many other works in Combinatorics : bijective proofs in matrix algebra (MacMahon Master theorem, inversion matrix formula, Jacobi identity, Cayley-Hamilton theorem), combinatorial theory for general (formal) orthogonal polynomials, reciprocal of Rogers-Ramanujan identities, graph theory (matching and chromatic polynomials).

In the references the subsequent articles "Heaps of pieces, 4 and 5" are listed as "in preparation" where the applications of the theory to solving the directed animal problem and statistical physics are supposed to be developed. I know that these parts of the theory have appeared in literature but I am sort of puzzled as to why the series of papers was not continued (searching for Heaps of pieces II or III or IV doesn't give results). Is there any survey of the full theory somewhere else?

Also, since I didn't feel like asking this in a separate question, is there any paper that proves classical theorems of dimers (Kasteleyn's theorem, Aztec diamond etc.) using Viennot's theory?

Answer by Igor Pak for What (if anything) happened to Viennot's theory of Heaps of pieces?

2010-03-12T06:45:21Z

Ok, this I know. Viennot basically invents lots of great stuff but rarely publishes his work. About "heaps of pieces" - this is a pretty little theory with very few original consequences. It is really equivalent to Cartier-Foata partially commutative monoid (available here). See Christian Krattenthaler's article for the connection and details. See there also some references to other recent papers.

Now, for many of Viennot's unpublished results, see his "Orthogonal polynomials..." book, which was unavailable for years, but is now on his web page. See there also several of his video lectures (mostly in French), where he outlined some interesting bijections based on the heaps (some related to various lattice animals were new to me, even if he may have come up with them some years ago - take a look). The reciprocal of R-R identities is an elegant single observation which he published separately: MR0989236. It really does not reprove the R-R identities, just gives a new combinatorial interpretation for one side using heaps of dimers (various related results were obtained by Andrews-Baxter a bit earlier).

About some recent applications outside of enumerative combinatorics. Philippe Marchal describes here that heaps of pieces easily imply David Wilson's theorem on Loop-erased random walks giving random spanning trees. Ellenberg and Tymoczko give a beautiful application to the diameter bound of certain Cayley graphs. Finally, in my paper with Matjaz Konvalinka, we use a heaps-of-pieces style bijection to give the "book proof" of the (non- and q-commutative) MacMahon Master theorem.

On your followup question regarding Kasteleyn's theorem and the Aztec diamond theorem - no, these are results of different kind, heaps don't really apply, at least as far as I know.

Answer by Tim Porter for What (if anything) happened to Viennot's theory of Heaps of pieces?

2010-03-12T11:28:20Z

There is considerable use made of, at least, the basic ideas in the theory of Discrete Event Systems. (This is lovely stuff if planning courses as it uses many ideas from abstract algebra and combinatorics, yet is visibly of application to interesting practical problems.) There is work by Gaubert and Mairesse on Tetris models.