Polynomial ideals for sandpiles and their Gröbner bases

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 configu...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2002-04, Vol.276 (1), p.1-15
Main Authors: Cori, Robert, Rossin, Dominique, Salvy, Bruno
Format: Article
Language:English
Subjects:
Algebra
Combinatorics
Combinatorics. Ordered structures
Critical phenomena
Exact sciences and technology
Games on graphs
Graph theory
Gröbner basis
Linear and multilinear algebra, matrix theory
Mathematics
Sandpile model
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(00)00397-2