Geodesic
Abelian networks. III: The critical group
Journal of Algebraic Combinatorics, Tome 43 (2016) no. 3, pp. 635-663.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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. For the first two parts see [the authors, SIAM J. Discrete Math. 30, No. 2, 856--874 (2016; Zbl 1356.68072); Sel. Math., New Ser. 22, No. 1, 319--340 (2016; Zbl 1369.68208)].
Classification : 05C25, 05C50, 20M14, 20M35, 68Q10
Keywords: abelian distributed processors, asynchronous computation, burning algorithm, chip firing, commutative monoid action, Laplacian lattice, sandpile group, script algorithm 
@article{JAC_2016__43_3_a4,
     author = {Bond, Benjamin and Levine, Lionel},
     title = {Abelian networks. {III:} {The} critical group},
     journal = {Journal of Algebraic Combinatorics},
     pages = {635--663},
     publisher = {mathdoc},
     volume = {43},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2016__43_3_a4/}
}
TY  - JOUR
AU  - Bond, Benjamin
AU  - Levine, Lionel
TI  - Abelian networks. III: The critical group
JO  - Journal of Algebraic Combinatorics
PY  - 2016
SP  - 635
EP  - 663
VL  - 43
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2016__43_3_a4/
LA  - en
ID  - JAC_2016__43_3_a4
ER  - 
%0 Journal Article
%A Bond, Benjamin
%A Levine, Lionel
%T Abelian networks. III: The critical group
%J Journal of Algebraic Combinatorics
%D 2016
%P 635-663
%V 43
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2016__43_3_a4/
%G en
%F JAC_2016__43_3_a4
Bond, Benjamin; Levine, Lionel. Abelian networks. III: The critical group. Journal of Algebraic Combinatorics, Tome 43 (2016) no. 3, pp. 635-663. http://geodesic.mathdoc.fr/item/JAC_2016__43_3_a4/