Clémence Magnien ; Ha Duong Phan ; Laurent Vuillon - Characterization of Lattices Induced by (extended) Chip Firing Games

dmtcs:2277 - Discrete Mathematics & Theoretical Computer Science, January 1, 2001, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001) - https://doi.org/10.46298/dmtcs.2277
Characterization of Lattices Induced by (extended) Chip Firing GamesArticle

Authors: Clémence Magnien 1; Ha Duong Phan 1; Laurent Vuillon 1

  • 1 Laboratoire d'informatique Algorithmique : Fondements et Applications

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.


Volume: DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
Section: Proceedings
Published on: January 1, 2001
Imported on: November 21, 2016
Keywords: 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]

6 Documents citing this article

Consultation statistics

This page has been seen 420 times.
This article's PDF has been downloaded 256 times.