×

Polynomial ideals for sandpiles and their Gröbner bases. (English) Zbl 1002.68105

Summary: A polynomial ideal encoding topplings in the abelian sandpile model on a graph is introduced. A Gröbner basis of this ideal is interpreted combinatorially in terms of well-connected subgraphs. This gives rise to algorithms to determine the identity and the operation in the group of recurrent configurations.

MSC:

68R10 Graph theory (including graph drawing) in computer science
13B10 Morphisms of commutative rings
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bak, P.; Tang, Chao; Wiesenfeld, K., Self-organized criticality, Phys. Rev. A Third Ser., 38, 1, 364-374 (1988) · Zbl 1230.37103
[2] Biggs, N. L., Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 1, 25-45 (1999) · Zbl 0919.05027
[3] N. Biggs, Chip firing on distance-regular graphs, Tech. Report LSE-CDAM-96-11, CDAM Research Report Series, June 1996.; N. Biggs, Chip firing on distance-regular graphs, Tech. Report LSE-CDAM-96-11, CDAM Research Report Series, June 1996.
[4] Björner, A.; Lovász, L.; Shor, P. W., Chip-firing games on graphs, European J. Combin., 12, 4, 283-291 (1991) · Zbl 0729.05048
[5] Cori, R.; Rossin, D., On the sandpile group of dual graphs, European J. Combin., 21, 447-459 (2000) · Zbl 0969.05034
[6] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms (1997), Springer: Springer New York
[7] Creutz, M., Abelian sandpiles, Comput. Phys., 5, 2, 198-203 (1991)
[8] Dhar, D.; Ruelle, P.; Sen, S.; Verma, D.-N., Algebraic aspects of abelian sandpile models, J. Phys. A, 28, 4, 805-831 (1995) · Zbl 0848.68062
[9] Dhar, D., Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613-1616 (1990) · Zbl 0943.82553
[10] Eisenbud, D.; Sturmfels, B., Binomial ideals, Duke Math. J., 84, 1, 1-45 (1996) · Zbl 0873.13021
[11] Mayr, E. W.; Meyer, A. R., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math., 46, 3, 305-329 (1982) · Zbl 0506.03007
[12] Moore, C.; Nilsson, M., The computational complexity of sandpiles, J. Statist. Phys., 96, 1-2, 205-224 (1999) · Zbl 0964.82037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.