Publication:5958333

DOI10.1016/S0304-3975(01)00119-0zbMATH Open0992.68226arXivmath/0010315OpenAlexW2051294537MaRDI QIDQ5958333FDOQ5958333

Eric Goles, M. Morvan, Thi Ha Duong Phan

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: In this paper, we study the dynamics of sand grains falling in sand piles. Usually sand piles are characterized by a decreasing integer partition and grain moves are described in terms of transitions between such partitions. We study here four main transition rules. The more classical one, introduced by Brylawski (1973) induces a lattice structure $L_B(n)$ (called dominance ordering) between decreasing partitions of a given integer n. We prove that a more restrictive transition rule, called SPM rule, induces a natural partition of L_B (n) in suborders, each one associated to a fixed point for SPM rule. In the second part, we extend the SPM rule in a natural way and obtain a model called Chip Firing Game (Goles and Kiwi, 1993). We prove that this new model has interesting properties: the induced order is a lattice, a natural greedoid can be associated to the model and it also defines a strongly convergent game. In the last section, we generalize the SPM rule in another way and obtain other lattice structure parametrized by some t: L(n,t), which form for -n+2 <= t <= n a decreasing sequence of lattices. For each t, we characterize the fixed point of L(n,t) and give the value of its maximal sized chain's lenght. We also note that L(n,-n+2) is the lattice of all compositions of n.

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

zbMATH Keywords

latticefixed pointinteger partitionsand pile modellinear chip firing gamemodel of Brylawski

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Self-organized criticality
• Balancing vectors in the max norm
• Longest chains in the lattice of integer partitions ordered by majorization
• The lattice of integer partitions
• Disks, Balls, and Walls: Analysis of a Combinatorial Game
• Games on line graphs and sand piles
• Sandpiles and order structure of integer partitions
• Greedoids

Cited In (15)

• Kadanoff sand pile model. Avalanche structure and wave shape
• Random Walks, Electric Networks and The Transience Class problem of Sandpiles
• On the emergence of regularities on one-dimensional decreasing sandpiles
• From sandpiles to sand automata
• Sandpile models and lattices: a comprehensive survey
• A survey on the stability of (extended) linear Sand Pile model
• Lattices generated by chip firing game models: criteria and recognition algorithms
• Sandpiles and order structure of integer partitions
• Emergence on Decreasing Sandpile Models
• Strict partitions and discrete dynamical systems
• Directed nonabelian sandpile models on trees
• Fixed-point forms of the parallel symmetric sandpile model
• Upward-closed hereditary families in the dominance order
• Computational Complexity of the Avalanche Problem on One Dimensional Kadanoff Sandpiles
• Strong emergence of wave patterns on Kadanoff sandpiles

This page was built for publication: The structure of a linear chip firing game and related models

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