TY - JOUR
T1 - Combinatorial aspects of sandpile models on wheel and fan graphs
AU - Selig, Thomas
N1 - Funding Information:
This work is partially supported by the National Natural Science Foundation of China , grant number 12101505 .
Publisher Copyright:
© 2022 Elsevier Ltd
PY - 2023/5
Y1 - 2023/5
N2 - We study combinatorial aspects of the sandpile model on wheel and fan graphs, seeking bijective characterisations of the model's recurrent configurations on these families. For wheel graphs, we exhibit a bijection between these recurrent configurations and the set of subgraphs of the cycle graph which maps the level of the configuration to the number of edges of the subgraph. This bijection relies on two key ingredients. The first consists in considering a stochastic variant of the standard Abelian sandpile model (ASM), rather than the ASM itself. The second ingredient is a mapping from a given recurrent state to a canonical minimal recurrent state, exploiting similar ideas to previous studies of the ASM on complete bipartite graphs and Ferrers graphs. We also show that on the wheel graph with 2n vertices, the number of recurrent states with level n is given by the first differences of the central Delannoy numbers. Finally, using similar tools, we exhibit a bijection between the set of recurrent configurations of the ASM on fan graphs and the set of subgraphs of the path graph containing the right-most vertex of the path. We show that these sets are also equinumerous with certain lattice paths, which we name Kimberling paths after the author of the corresponding entry in the Online Encyclopedia of Integer Sequences.
AB - We study combinatorial aspects of the sandpile model on wheel and fan graphs, seeking bijective characterisations of the model's recurrent configurations on these families. For wheel graphs, we exhibit a bijection between these recurrent configurations and the set of subgraphs of the cycle graph which maps the level of the configuration to the number of edges of the subgraph. This bijection relies on two key ingredients. The first consists in considering a stochastic variant of the standard Abelian sandpile model (ASM), rather than the ASM itself. The second ingredient is a mapping from a given recurrent state to a canonical minimal recurrent state, exploiting similar ideas to previous studies of the ASM on complete bipartite graphs and Ferrers graphs. We also show that on the wheel graph with 2n vertices, the number of recurrent states with level n is given by the first differences of the central Delannoy numbers. Finally, using similar tools, we exhibit a bijection between the set of recurrent configurations of the ASM on fan graphs and the set of subgraphs of the path graph containing the right-most vertex of the path. We show that these sets are also equinumerous with certain lattice paths, which we name Kimberling paths after the author of the corresponding entry in the Online Encyclopedia of Integer Sequences.
UR - http://www.scopus.com/inward/record.url?scp=85144785553&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2022.103663
DO - 10.1016/j.ejc.2022.103663
M3 - Article
AN - SCOPUS:85144785553
SN - 0195-6698
VL - 110
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103663
ER -