Discrete Math Seminar: Yvan Le Borgne

The sandpile model was introduced by physicists Bak, Tang and Wiesenfeld in 1988. Then it was identified as a prototype of self organized criticality. This discrete model of diffusion is generally defined on any connected graph, and a configuration/state corresponds to a distribution of grains on vertices. Here are some of its general properties. It induces a Markov chain with uniform stationary distribution on some recurrent configurations in bijection with spanning trees. The distribution of external activity of Tutte polynomial corresponds to the distribution of the number of grains. Addition of recurrent configurations leads to a finite abelian group for each graph, sometimes called in other contexts the critical group or the Picard's group.

During this talk, I will focus on the case of complete and bipartite complete graphs. The symmetries of these graphs simplify a lot the analysis but leads, according to me, to not so completely trivial results. A study related to the evolution of the Markov chain to the recurrent configurations simply leads to an apparently not so well-known extension, due to Chottin (1975), of a classical cyclic lemma used to count Dyck words. The analysis of Dhar's criterion, testing recurrence of a given configuration, simply leads to bistatistics related to the q,t-Catalan numbers studied by Bergeron, Garsia, Haglund and Haiman in their study of the space of diagonal harmonics. On the complete graphs, we obtain an algorithm of linear arithmetic complexity for the rank parameter introduced by Baker and Norine in 2007 for their analogue of Riemann-Roch theorem for graphs.

Based on joint works with Mark Dukes, Michele D'adderio, Jean-Christophe Aval, Angela Hicks and Robert Cori. [arXiv:1208.0024,arXiv:1301.4803, arXiv:1307.7740, arXiv:1308.5325]