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, Chengdu, China, February 28 – March 2, 2025
Editors	Shin-ichi Nakano, Mingyu Xiao
Publisher	Springer Singapore
Number of pages	19
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
Publisher	Springer Singapore
Volume	15411
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

1 Finished
1 Active

Towards a combinatorial theory of sandpile models
Selig, T.
1/01/23 → 31/12/25
Project: Internal Research Project
Stochastic variants of the Abelian sandpile model
Selig, T.
1/01/22 → 31/12/24
Project: Governmental Research Project

1 Participating in an event e.g. a conference, workshop, …
1 Presentation at conference/workshop/seminar

Abelian and stochastic sandpile models on complete bipartite graphs
Thomas Selig (Speaker)
2 Mar 2025
Activity: Talk or presentation › Presentation at conference/workshop/seminar
The 19th International Conference and Workshops on Algorithms and Computation
Thomas Selig (Participant)
28 Feb 2025 → 2 Mar 2025
Activity: Participating in or organising an event › Participating in an event e.g. a conference, workshop, …

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, Chengdu, China, February 28 – March 2, 2025 (Lecture Notes in Computer Science; Vol. 15411). 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, Chengdu, China, February 28 – March 2, 2025. editor / Shin-ichi Nakano ; Mingyu Xiao. Springer Singapore, 2025. (Lecture Notes in Computer Science).

@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",

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",

publisher = "Springer Singapore",

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

booktitle = "WALCOM: Algorithms and Computation",

note = "The 19th International Conference and Workshops on Algorithms and Computation, WALCOM 2025 ; Conference date: 28-02-2025 Through 02-03-2025",

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, Chengdu, China, February 28 – March 2, 2025. Lecture Notes in Computer Science, vol. 15411, Springer Singapore, 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, Chengdu, China, February 28 – March 2, 2025. ed. / Shin-ichi Nakano; Mingyu Xiao. Springer Singapore, 2025. (Lecture Notes in Computer Science; Vol. 15411).

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

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

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, Chengdu, China, February 28 – March 2, 2025. Springer Singapore. 2025. (Lecture Notes in Computer Science). 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

Fingerprint

Projects

Towards a combinatorial theory of sandpile models

Stochastic variants of the Abelian sandpile model

Activities

Abelian and stochastic sandpile models on complete bipartite graphs

The 19th International Conference and Workshops on Algorithms and Computation

Cite this