Coding distributive lattices with Edge Firing Games.

DOI10.1016/S0020-0190(01)00319-2MaRDI QIDQ1853051zbMATH OpenFDO

Authors Matthieu Latapy, Clémence Magnien

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0110214

zbMATH Keywords

Combinatorial problemsDistributive latticeChip Firing GameDiscrete dynamical modelEdge Firing GameOrientations of graphsSource Reversal Game

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Abstract: In this note, we show that any distributive lattice is isomorphic to the set of reachable configurations of an Edge Firing Game. Together with the result of James Propp, saying that the set of reachable configurations of any Edge Firing Game is always a distributive lattice, this shows that the two concepts are equivalent.

Recommendations

• Characterization of simple edge-firing games.
• scientific article; zbMATH DE number 1741026
• Lattices generated by chip firing game models: criteria and recognition algorithms
• The lattice structure of chip firing games and related models
• Classes of lattices induced by chip firing (and sandpile) dynamics.

Cites work

• scientific article; zbMATH DE number 3957181 (Why is no real title available?)
• scientific article; zbMATH DE number 3437182 (Why is no real title available?)
• scientific article; zbMATH DE number 194916 (Why is no real title available?)
• scientific article; zbMATH DE number 3010765 (Why is no real title available?)
• scientific article; zbMATH DE number 3411070 (Why is no real title available?)
• scientific article; zbMATH DE number 3411071 (Why is no real title available?)
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Chip-firing games on graphs
• On reorienting graphs by pushing down maximal vertices
• The lattice structure of chip firing games and related models

Cited in

(5)

• Characterization of simple edge-firing games.
• Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
• Decomposition theorem on matchable distributive lattices
• A geometric approach to acyclic orientations
• On reorienting graphs by pushing down maximal vertices. II

This page was built for publication: Coding distributive lattices with Edge Firing Games.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853051)