What (if anything) happened to Viennot's theory of Heaps of pieces? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:05:24Z http://mathoverflow.net/feeds/question/17946 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17946/what-if-anything-happened-to-viennots-theory-of-heaps-of-pieces What (if anything) happened to Viennot's theory of Heaps of pieces? Gjergji Zaimi 2010-03-12T04:22:12Z 2010-03-12T11:28:20Z <p>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). </p> <p>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?</p> <p>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?</p> http://mathoverflow.net/questions/17946/what-if-anything-happened-to-viennots-theory-of-heaps-of-pieces/17958#17958 Answer by Igor Pak for What (if anything) happened to Viennot's theory of Heaps of pieces? Igor Pak 2010-03-12T06:45:21Z 2010-03-12T06:45:21Z <p>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 <a href="http://www.mat.univie.ac.at/~slc/books/cartfoa.html" rel="nofollow">here</a>). See Christian Krattenthaler's <a href="http://www.mat.univie.ac.at/~kratt/artikel/heaps.html" rel="nofollow">article</a> for the connection and details. See there also some references to other recent papers. </p> <p>Now, for many of Viennot's unpublished results, see his "Orthogonal polynomials..." book, which was unavailable for years, but is now on his <a href="http://web.mac.com/xgviennot/Xavier_Viennot/Bienvenue.html" rel="nofollow">web page</a>. 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). </p> <p>About some recent applications outside of enumerative combinatorics. Philippe Marchal describes <a href="http://algo.inria.fr/seminars/sem00-01/marchal.html" rel="nofollow">here</a> that heaps of pieces easily imply <a href="http://dbwilson.com/ja/tau.ps" rel="nofollow">David Wilson's theorem</a> on <a href="http://en.wikipedia.org/wiki/Loop-erased_random_walk" rel="nofollow">Loop-erased random walks</a> giving random spanning trees. Ellenberg and Tymoczko give a <a href="http://arxiv.org/abs/math.GR/0510506" rel="nofollow">beautiful application</a> to the diameter bound of certain Cayley graphs. Finally, in <a href="http://arxiv.org/abs/math/0607737" rel="nofollow">my paper</a> with Matjaz Konvalinka, we use a heaps-of-pieces style bijection to give the "book proof" of the (non- and q-commutative) <a href="http://en.wikipedia.org/wiki/MacMahon_Master_theorem" rel="nofollow">MacMahon Master theorem</a>. </p> <p>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. </p> http://mathoverflow.net/questions/17946/what-if-anything-happened-to-viennots-theory-of-heaps-of-pieces/17974#17974 Answer by Tim Porter for What (if anything) happened to Viennot's theory of Heaps of pieces? Tim Porter 2010-03-12T11:28:20Z 2010-03-12T11:28:20Z <p>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. </p>