Chip-Firing,Antimatroids, and Polyhedra |
| |
| Institution: | 1. Fachbereich Mathematik, Universität Salzburg, Hellbrunnerstr. 34, 5020 Salzburg, Austria;2. Institut für Finanzmathematik, Johannes Kepler Universität Linz, Altenbergerstr. 69, 4040 Linz, Austria;3. Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria;1. Centre for Research in Mathematics, University of Western Sydney, Australia;2. Centre for Analysis of Time Series, London School of Economics, UK;1. University of California, Berkeley, Berkeley, CA 94720, United States of America;2. Department of Mathematics and Computer Science, Ursinus College, Collegeville, PA 19426, United States of America;1. Faculty of Mathematics and Computer Science, Jagiellonian University, Łojasiewicza 6, PL-30-348 Kraków, Poland;2. Institute of Mathematics, Pedagogical University of Cracow, Podchora̧żych 2, PL-30-084 Kraków, Poland;3. Department of Mathematics, University of Nebraska, Lincoln, NE 68588-0130, USA |
| |
| Abstract: | Starting from the chip-firing game of Björner and Lovász we consider a generalization to vector addition systems that still admit algebraic structures as sandpile group or sandpile monoid. Every such vector addition language yields an antimatroid. We show that conversely every antimatroid can be represented this way. The inclusion order on the feasible sets of an antimatroid is an upper locally distributive lattice. We characterize polyhedra, which carry an upper locally distributive structure and show that they can be modelled by chip-firing games with gains and losses. At the end we point out a connection to a membership problem discussed by Korte and Lovász. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
