Abelian and stochastic sandpile models on complete bipartite graphs

Thomas Selig; Haoyue Zhu

doi:10.1007/978-981-96-2845-2_21

Abelian and stochastic sandpile models on complete bipartite graphs

Thomas Selig^*
, Haoyue Zhu

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

Abstract

In the sandpile model, vertices of a graph are allocated grains of sand. At each unit of time, a grain is added to a randomly chosen vertex. If that causes its number of grains to exceed its degree, that vertex is called unstable, and topples. In the Abelian sandpile model (ASM), topplings are deterministic, whereas in the stochastic sandpile model (SSM) they are random. We study the ASM and SSM on complete bipartite graphs. For the SSM, we provide a stochastic version of Dhar's burning algorithm to check if a given (stable) configuration is recurrent or not, with linear complexity. We also exhibit a bijection between sorted recurrent configurations and pairs of compatible Ferrers diagrams. We then provide a similar bijection for the ASM, and also interpret its recurrent configurations in terms of labelled Motzkin paths.

Original language	English
Title of host publication	WALCOM: Algorithms and Computation
Subtitle of host publication	19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025, Proceedings
Editors	Shin-ichi Nakano, Mingyu Xiao
Publisher	Springer Singapore
Pages	326-345
Number of pages	20
ISBN (Electronic)	978-981-96-2845-2
ISBN (Print)	978-981-96-2844-5
DOIs	https://doi.org/10.1007/978-981-96-2845-2_21
Publication status	Published - 21 Feb 2025
Event	The 19th International Conference and Workshops on Algorithms and Computation - University of Electronic Science and Technology of China, Chengdu, China Duration: 28 Feb 2025 → 2 Mar 2025 Conference number: 19 https://tcsuestc.com/walcom2025/index.html

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	15411 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The 19th International Conference and Workshops on Algorithms and Computation
Abbreviated title	WALCOM 2025
Country/Territory	China
City	Chengdu
Period	28/02/25 → 2/03/25
Internet address	https://tcsuestc.com/walcom2025/index.html

Keywords

Sandpile model
Complete bipartite graphs
Recurrent configurations
Ferrers diagrams
Motzkin paths

Access to Document

10.1007/978-981-96-2845-2_21

Cite this

Selig, T., & Zhu, H. (2025). Abelian and stochastic sandpile models on complete bipartite graphs. In S. Nakano, & M. Xiao (Eds.), WALCOM: Algorithms and Computation: 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025, Proceedings (pp. 326-345). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15411 LNCS). Springer Singapore. https://doi.org/10.1007/978-981-96-2845-2_21

Selig, Thomas ; Zhu, Haoyue. / Abelian and stochastic sandpile models on complete bipartite graphs. WALCOM: Algorithms and Computation: 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025, Proceedings. editor / Shin-ichi Nakano ; Mingyu Xiao. Springer Singapore, 2025. pp. 326-345 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7afbecca4ff54dc5a198c0b9ea85c242,

title = "Abelian and stochastic sandpile models on complete bipartite graphs",

abstract = "In the sandpile model, vertices of a graph are allocated grains of sand. At each unit of time, a grain is added to a randomly chosen vertex. If that causes its number of grains to exceed its degree, that vertex is called unstable, and topples. In the Abelian sandpile model (ASM), topplings are deterministic, whereas in the stochastic sandpile model (SSM) they are random. We study the ASM and SSM on complete bipartite graphs. For the SSM, we provide a stochastic version of Dhar's burning algorithm to check if a given (stable) configuration is recurrent or not, with linear complexity. We also exhibit a bijection between sorted recurrent configurations and pairs of compatible Ferrers diagrams. We then provide a similar bijection for the ASM, and also interpret its recurrent configurations in terms of labelled Motzkin paths.",

keywords = "Sandpile model, Complete bipartite graphs, Recurrent configurations, Ferrers diagrams, Motzkin paths",

author = "Thomas Selig and Haoyue Zhu",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.; The 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025 ; Conference date: 28-02-2025 Through 02-03-2025",

year = "2025",

month = feb,

day = "21",

doi = "10.1007/978-981-96-2845-2\_21",

language = "English",

isbn = "978-981-96-2844-5",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Singapore",

pages = "326--345",

editor = "Shin-ichi Nakano and Mingyu Xiao",

booktitle = "WALCOM: Algorithms and Computation",

url = "https://tcsuestc.com/walcom2025/index.html",

}

Selig, T & Zhu, H 2025, Abelian and stochastic sandpile models on complete bipartite graphs. in S Nakano & M Xiao (eds), WALCOM: Algorithms and Computation: 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 15411 LNCS, Springer Singapore, pp. 326-345, The 19th International Conference and Workshops on Algorithms and Computation, Chengdu, China, 28/02/25. https://doi.org/10.1007/978-981-96-2845-2_21

Abelian and stochastic sandpile models on complete bipartite graphs. / Selig, Thomas; Zhu, Haoyue.
WALCOM: Algorithms and Computation: 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025, Proceedings. ed. / Shin-ichi Nakano; Mingyu Xiao. Springer Singapore, 2025. p. 326-345 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15411 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Abelian and stochastic sandpile models on complete bipartite graphs

AU - Selig, Thomas

AU - Zhu, Haoyue

N1 - Conference code: 19

PY - 2025/2/21

Y1 - 2025/2/21

N2 - In the sandpile model, vertices of a graph are allocated grains of sand. At each unit of time, a grain is added to a randomly chosen vertex. If that causes its number of grains to exceed its degree, that vertex is called unstable, and topples. In the Abelian sandpile model (ASM), topplings are deterministic, whereas in the stochastic sandpile model (SSM) they are random. We study the ASM and SSM on complete bipartite graphs. For the SSM, we provide a stochastic version of Dhar's burning algorithm to check if a given (stable) configuration is recurrent or not, with linear complexity. We also exhibit a bijection between sorted recurrent configurations and pairs of compatible Ferrers diagrams. We then provide a similar bijection for the ASM, and also interpret its recurrent configurations in terms of labelled Motzkin paths.

AB - In the sandpile model, vertices of a graph are allocated grains of sand. At each unit of time, a grain is added to a randomly chosen vertex. If that causes its number of grains to exceed its degree, that vertex is called unstable, and topples. In the Abelian sandpile model (ASM), topplings are deterministic, whereas in the stochastic sandpile model (SSM) they are random. We study the ASM and SSM on complete bipartite graphs. For the SSM, we provide a stochastic version of Dhar's burning algorithm to check if a given (stable) configuration is recurrent or not, with linear complexity. We also exhibit a bijection between sorted recurrent configurations and pairs of compatible Ferrers diagrams. We then provide a similar bijection for the ASM, and also interpret its recurrent configurations in terms of labelled Motzkin paths.

KW - Sandpile model

KW - Complete bipartite graphs

KW - Recurrent configurations

KW - Ferrers diagrams

KW - Motzkin paths

UR - https://www.scopus.com/pages/publications/86000222657

U2 - 10.1007/978-981-96-2845-2_21

DO - 10.1007/978-981-96-2845-2_21

M3 - Conference Proceeding

SN - 978-981-96-2844-5

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 326

EP - 345

BT - WALCOM: Algorithms and Computation

A2 - Nakano, Shin-ichi

A2 - Xiao, Mingyu

PB - Springer Singapore

T2 - The 19th International Conference and Workshops on Algorithms and Computation

Y2 - 28 February 2025 through 2 March 2025

ER -

Selig T, Zhu H. Abelian and stochastic sandpile models on complete bipartite graphs. In Nakano S, Xiao M, editors, WALCOM: Algorithms and Computation: 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025, Proceedings. Springer Singapore. 2025. p. 326-345. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-96-2845-2_21

Abelian and stochastic sandpile models on complete bipartite graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Towards a combinatorial theory of sandpile models

Stochastic variants of the Abelian sandpile model