Abelian networks. III: The critical group

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

Authors: Benjamin Bond, Lionel Levine 

Publication date: 27 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (12)

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

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)