TY - JOUR

T1 - Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a Cyclic Lemma

AU - Aval, Jean-Christophe

AU - D'Adderio, Michele

AU - Dukes, Mark

AU - Le Borgne, Yvan

PY - 2016/2/1

Y1 - 2016/2/1

N2 - We introduce two operators on stable configurations of the sandpile model that provide an algorithmic bijection between recurrent and parking congurations. This bijection preserves their equivalence classes with respect to the sandpile group. The study of these operators in the special case of the complete bipartite graph K m;n naturally leads to a generalization of the well known Cyclic Lemma of Dvoretsky and Motzkin, via pairs of periodic bi-in nite paths in the plane having slightly different slopes. We achieve our results by interpreting the action of these operators as an action on a point in the grid Z2 which is pointed to by one of these pairs of paths. Our Cyclic lemma allows us to enumerate several classes of polyominoes, and therefore builds on the work of Irving and Rattan (2009), Chapman et al. (2009), and Bonin et al. (2003).

AB - We introduce two operators on stable configurations of the sandpile model that provide an algorithmic bijection between recurrent and parking congurations. This bijection preserves their equivalence classes with respect to the sandpile group. The study of these operators in the special case of the complete bipartite graph K m;n naturally leads to a generalization of the well known Cyclic Lemma of Dvoretsky and Motzkin, via pairs of periodic bi-in nite paths in the plane having slightly different slopes. We achieve our results by interpreting the action of these operators as an action on a point in the grid Z2 which is pointed to by one of these pairs of paths. Our Cyclic lemma allows us to enumerate several classes of polyominoes, and therefore builds on the work of Irving and Rattan (2009), Chapman et al. (2009), and Bonin et al. (2003).

KW - sandpile model

KW - complete graphs

KW - complete bipartite graph

KW - cyclic lemma

UR - http://www.sciencedirect.com/science/article/pii/S0196885815001062

UR - http://www.sciencedirect.com/science/journal/01968858

M3 - Article

VL - 73

SP - 59

EP - 98

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

SN - 0196-8858

ER -