eng
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
2001-01-01
DMTCS Proceedings vol. AA,...
Proceedings
10.46298/dmtcs.2277
2277
journal article
Characterization of Lattices Induced by (extended) Chip Firing Games
ClĂ©mence Magnien
Ha Duong Phan
Laurent Vuillon
The Chip Firing Game (CFG) is a discrete dynamical model used in physics, computer science and economics. It is known that the set of configurationsreachable from an initial configuration (this set is called the \textitconfiguration space) can be ordered as a lattice. We first present a structural result about this model, which allows us to introduce some useful tools for describing those lattices. Then we establish that the class of lattices that are the configuration space of a CFG is strictly between the class of distributive lattices and the class of upper locally distributive (or ULD) lattices. Finally we propose an extension of the model, the \textitcoloured Chip Firing Game, which generates exactly the class of ULD lattices.
https://dmtcs.episciences.org/2277/pdf
Sand Pile Model
Discrete Dynamical Model
Lattice
Chip Firing Game
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]