27
$\begingroup$

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?

Improve this question
$\endgroup$
1

5 Answers 5

Reset to default
24
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 9
    $\begingroup$ Prof. Viennot does have 56 MathSciNet publications. If this counts as "rarely publishing his work", then he must be a prolific worker! (A glance at his webpage seems to indicate that this is indeed the case.) $\endgroup$
    – Pete L. Clark
    Commented Mar 12, 2010 at 7:46
5
$\begingroup$

Heaps are significant in the theory (especially the combinatorial theory) of minuscule representations of Lie algebras. I guess Stembridge in his 1996 paper "On the fully commutative elements of Coxeter group" might have been the first to recognize this? But for instance heaps play a central role in the recent book "Combinatorics of Minuscule Representations" by R.M. Green.

Improve this answer
$\endgroup$
4
$\begingroup$

The Cartier-Foata free partially commutative monoids are used in computer science in modeling concurrent computation under the name trace monoids. See, for example, the Wikipedia article on trace monoids, https://en.wikipedia.org/wiki/Trace_monoid.

Improve this answer
$\endgroup$
4
$\begingroup$

There has been recent work by Tyler Helmuth which applies Viennot's theory to statistical mechanics and in particular finding new expression for the two point function of Ising-like systems. See his article: https://arxiv.org/abs/1209.3996

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Also heaps are analyzed from math-phys point of view here: arxiv.org/abs/math/9905190 Statistical properties of braid groups in locally free approximation A.M. Vershik, S. Nechaev, R. Bikbov $\endgroup$
    – Alexander Chervov
    Commented Mar 16 at 20:27
  • $\begingroup$ Thanks for the reference which I didn't know. Maybe this should be posted as an answer rather than a comment. $\endgroup$
    – Abdelmalek Abdesselam
    Commented Mar 17 at 14:57
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .