Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma

DOI10.1016/J.AAM.2015.09.018zbMATH Open1328.05118arXiv1307.7740OpenAlexW1718672927WikidataQ124989021 ScholiaQ124989021MaRDI QIDQ900982FDOQ900982

Mark Dukes, J.-C. Aval, Michele D'Adderio, Yvan Le Borgne

Publication date: 23 December 2015

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: We introduce two operators on stable configurations of the sandpile model that provide an algorithmic bijection between recurrent and parking configurations. 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-infinite 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 $mathbb{Z}^2$ 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).

Full work available at URL: https://arxiv.org/abs/1307.7740

Recommendations

• The sand-pile model and Tutte polynomials
• The sandpile model on \(K_{m,n}\) and the rank of its configurations
• Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a \(q,t\)-Narayana polynomial
• Combinatorial aspects of sandpile models on wheel and Fan graphs
• The sandpile model on a bipartite graph, parallelogram polyominoes, and a \(q,t\)-Narayana polynomial

zbMATH Keywords

sandpile modelcomplete bipartite graphcomplete graphscyclic lemma

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Combinatorial aspects of matroids and geometric lattices (05B35) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• On the sandpile group of dual graphs
• Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a \(q,t\)-Narayana polynomial
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Statistics on parallelogram polyominoes and a \(q,t\)-analogue of the Narayana numbers
• A problem of arrangements
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Une demonstration combinatoire de la formule de Lagrange à deux variables
• Simple formulas for lattice paths avoiding certain periodic staircase boundaries
• The number of lattice paths below a cyclically shifting boundary
• Combinatorics of labelled parallelogram polyominoes

Cited In (10)

• The abelian sandpile model on Ferrers graphs -- a classification of recurrent configurations
• The sandpile model on the complete split graph, Motzkin words, and tiered parking functions
• Title not available (Why is that?)
• Decomposing recurrent states of the Abelian sandpile model
• EW-tableaux, Le-tableaux, tree-like tableaux and the abelian sandpile model
• Parallelogram polyominoes and rectangular EW-tableaux: Correspondences through the Sandpile model
• The sandpile model on \(K_{m,n}\) and the rank of its configurations
• A maximizing characteristic for critical configurations of chip-firing games on digraphs
• Decomposing recurrent states of the abelian sandpile model
• Combinatorial aspects of sandpile models on wheel and Fan graphs

This page was built for publication: Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q900982)