Metraipolis › archive › dc_c75c7e5bf3ed
Primitive periods in greedy chip-firing games — arXiv:2610.08949
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.08949
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:43:49.723Z
- SHA-256 of the archived text
19f898bb2a687f4d1cfc388a497fcd2eef2b6c816231c544ca36a5624e59a235- Stable URL of this page
https://metraipolis.com/documento/dc_c75c7e5bf3ed
How to cite
Primitive periods in greedy chip-firing games — arXiv:2610.08949 — arXiv (en), https://arxiv.org/abs/2610.08949 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c75c7e5bf3ed (Metraipolis archive dc_c75c7e5bf3ed, sha256 19f898bb2a687f4d1cfc388a497fcd2eef2b6c816231c544ca36a5624e59a235)
BibTeX
@misc{dcc75c7e5bf3ed,
title = {Primitive periods in greedy chip-firing games — arXiv:2610.08949},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.08949},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c75c7e5bf3ed; sha256 19f898bb2a687f4d1cfc388a497fcd2eef2b6c816231c544ca36a5624e59a235},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08949. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a finite irreducible rational transition matrix $P=(P_{ij})$ on $n$ states, the hunger game introduced by Li and Propp is a greedy chip-firing process in which each state $i$ carries a real-valued hunger $h_i$. At each step, a state $i$ of maximal hunger is selected, with ties resolved by a fixed order on the states. Firing $i$ subtracts one from its hunger and then adds $P_{ij}$ to the hunger of each state $j$. Let $\pi$ be the stationary distribution of $P$, and let $T$ be the least positive integer such that $T\pi$ is integral. We prove that every periodic orbit has least period $T$, with state $i$ firing $T\pi_i$ times, and that the set of periodic states of total hunger zero tiles the corresponding hyperplane by lattice translations. These results settle two conjectures of Li and Propp. We also prove an analogous least-period theorem for nontrivial periodic orbits of fixed-priority chip-firing on finite strongly connected digraphs, another greedy chip-firing model. We then find a connection between the hunger game and the chairman assignment problem: the greedy rule that always chooses the state furthest below its proportional target is precisely a rank-one hunger game. Motivated by this application and related allocation rules, we generalize the hunger game by assigning each state a score that is a nondecreasing function of its hunger and firing a state of maximal score each time. For these monotone-score hunger games, we prove that every periodic orbit still has least period $T$ and give a sufficient condition for eventual periodicity from every initial state.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.08949 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:17:00.173Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).