Firing Patterns in the Parallel Chip-Firing Game - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2014

Firing Patterns in the Parallel Chip-Firing Game

Résumé

The $\textit{parallel chip-firing game}$ is an automaton on graphs in which vertices "fire'' chips to their neighbors. This simple model, analogous to sandpiles forming and collapsing, contains much emergent complexity and has connections to different areas of mathematics including self-organized criticality and the study of the sandpile group. In this work, we study $\textit{firing sequences}$, which describe each vertex's interaction with its neighbors in this game. Our main contribution is a complete characterization of the periodic firing sequences that can occur in a game, which have a surprisingly simple combinatorial description. We also obtain other results about local behavior of the game after introducing the concept of $\textit{motors}$.
Le $\textit{parallel chip-firing game}$, c’est une automate sur les graphiques, dans lequel les sommets “tirent” des jetons à leurs voisins. Ce modèle simple, semblable aux tas de sable qui forment et s’affaissent, contient beaucoup de complexité émergente et a des connections avec différents domaines de mathématiques, incluant le $\textit{self-organized criticality}$ et l’étude du $\textit{sandpile group}$. Dans ce projet, on étudie les $\textit{firing sequences}$, qui décrivent les interactions de chaque sommet avec ses voisins dans le jeu. Notre contribution principale est une caractérisation complète des séquences de tir qui peuvent arriver dans une jeu, qui ont une description combinatoire assez simple. Nous obtenons aussi d'autres résultats sur le conduite locale du jeu après l’introduction du concept des $\textit{motors}$.
Fichier principal
Vignette du fichier
dmAT0147.pdf (382.13 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01207550 , version 1 (01-10-2015)

Identifiants

Citer

Ziv Scully, Tian-Yi Jiang, Yan X. Zhang. Firing Patterns in the Parallel Chip-Firing Game. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. pp.537-548, ⟨10.46298/dmtcs.2421⟩. ⟨hal-01207550⟩

Collections

INSMI TDS-MACS
124 Consultations
1149 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More