Rotor-Routing Induces the Only Consistent Sandpile Torsor Structure on Plane Graphs
| Autor: | Ganguly, Ankan, McDonough, Alex |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1017/fms.2023.77 |
| Popis: | We make precise and prove a conjecture of Klivans about actions of the sandpile group on spanning trees. More specifically, the conjecture states that there exists a unique ``suitably nice'' sandpile torsor structure on plane graphs which is induced by rotor-routing. First, we rigorously define a sandpile torsor algorithm (on plane graphs) to be a map which associates each plane graph (i.e., planar graph with an appropriate ribbon structure) with a free transitive action of its sandpile group on its spanning trees. Then, we define a notion of consistency, which requires a torsor algorithm to be preserved with respect to a certain class of contractions and deletions. Using these definitions, we show that the rotor-routing sandpile torsor algorithm is consistent. Furthermore, we demonstrate that there are only three other consistent algorithms on plane graphs, which all have the same structure as rotor-routing. We also define sandpile torsor algorithms on regular matroids and suggest a notion of consistency in this context. We conjecture that the Backman-Baker-Yuen algorithm is consistent, and that there are only three other consistent sandpile torsor algorithms on regular matroids, all with the same structure. Comment: Extended Abstract Accepted to FPSAC 2022. The second version adjusts some wording and notation for clarity and adds an example/figure. The third version makes some minor changes, adds a few references, and revises the abstract |
| Databáze: | arXiv |
| Externí odkaz: |
|