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

Chip Firing GameCombinatorial problemsDiscrete dynamical modelDistributive latticeEdge Firing GameOrientations of graphsSource Reversal Game

Mathematics Subject Classification ID

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

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

• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Chip-firing games on graphs
• 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?)
• On reorienting graphs by pushing down maximal vertices
• The lattice structure of chip firing games and related models

Cited in

(6)

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

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)