Abelian networks. III: The critical group

DOI10.1007/S10801-015-0648-4zbMATH Open1336.05057OpenAlexW2964253584MaRDI QIDQ289043FDOQ289043

Authors Benjamin Bond, Lionel Levine 

Publication date 27 May 2016

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

abelian distributed processorsasynchronous computationburning algorithmchip firingcommutative monoid actionLaplacian latticesandpile groupscript algorithm

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Commutative semigroups (20M14) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: The critical group of an abelian network is a finite abelian group that governs the behavior of the network on large inputs. It generalizes the sandpile group of a graph. We show that the critical group of an irreducible abelian network acts freely and transitively on recurrent states of the network. We exhibit the critical group as a quotient of a free abelian group by a subgroup containing the image of the Laplacian, with equality in the case that the network is rectangular. We generalize Dhar's burning algorithm to abelian networks, and estimate the running time of an abelian network on an arbitrary input up to a constant additive error.

Recommendations

• Abelian networks IV. Dynamics of nonhalting networks
• Abelian networks. I: Foundations and examples
• On the identity of the sandpile group
• Abelian networks. II: Halting on all inputs
• Polynomial ideals for sandpiles and their Gröbner bases

Cites work

• scientific article; zbMATH DE number 3133558 (Why is no real title available?)
• scientific article; zbMATH DE number 2012819 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• A finite group attached to the laplacian of a graph
• A theory of transformation monoids: combinatorics and representation theory
• Abelian networks. I: Foundations and examples
• Abelian networks. II: Halting on all inputs
• Algebraic and combinatorial aspects of sandpile monoids on directed graphs
• Arithmetical graphs
• Asymmetric Abelian sandpile models
• Bigraphical arrangements
• Chip-Firing and Rotor-Routing on Directed Graphs
• Chip-firing and energy minimization on M-matrices
• Chip-firing and the critical group of a graph
• Chip-firing games, potential theory on graphs, and spanning trees
• Commutative actions.
• Critical groups of simplicial complexes
• Generalized loop-erased random walks and approximate reachability
• On the structure of semigroups
• Primer for the algebraic geometry of sandpiles
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Rotor walks and Markov chains
• Self-organized critical state of sandpile automaton models
• Simplicial matrix-tree theorems
• Simulating a Random Walk with Constant Error
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• The rotor-router model on regular trees
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Two-variable zeta-functions on graphs and Riemann-Roch theorems

Cited in

(12)

• The sandpile group of a polygon flower
• Abelian networks IV. Dynamics of nonhalting networks
• Uniform threshold for fixation of the stochastic sandpile model on the line
• Absorbing-state phase transition and activated random walks with unbounded capacities
• The sandpile group of polygon rings and twisted polygon rings
• Abelian sandpile model and Biggs-Merino polynomial for directed graphs
• Abelian networks. II: Halting on all inputs
• Abelian logic gates
• Sorting via chip-firing
• Abelian networks. I: Foundations and examples
• Sorting via chip-firing
• Hyperedge channels are abelian

This page was built for publication: Abelian networks. III: The critical group

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