Abelian and stochastic sandpile models on complete bipartite graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909319082016768 |
|---|---|
| author | Selig, Thomas Zhu, Haoyue |
| author_facet | Selig, Thomas Zhu, Haoyue |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11811 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Abelian and stochastic sandpile models on complete bipartite graphs Selig, Thomas Zhu, Haoyue Combinatorics Discrete Mathematics Probability 05A19 (Primary) 05A15, 05B50, 60J10 (Secondary) 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. |
| title | Abelian and stochastic sandpile models on complete bipartite graphs |
| topic | Combinatorics Discrete Mathematics Probability 05A19 (Primary) 05A15, 05B50, 60J10 (Secondary) |
| url | https://arxiv.org/abs/2409.11811 |