zbMATH — the first resource for mathematics

Chip-firing and Riemann-Roch theory for directed graphs. (English) Zbl 1274.05189
Nešetřil, Jarik (ed.) et al., Extended abstracts of the sixth European conference on combinatorics, graph theory and applications, EuroComb 2011, Budapest, Hungary, August 29 – September 2, 2011. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 38, 63-68 (2011).
Summary: Baker and Norine developed a graph-theoretic analogue of the classical Riemann-Roch theorem. Amini and Manjunath extended their criteria to all full-dimensional lattices orthogonal to the all ones vector. We show that Amini and Manjunath’s criteria hold for all full-dimensional lattices orthogonal to some positive vector and study some combinatorial examples of such lattices. Two distinct generalizations of the chip-firing game of Baker and Norine to directed graphs are provided. We describe how the “row” chip-firing game is related to the sandpile model and the “column” chip-firing game is related to directed \(G\)-parking functions. We finish with a discussion of arithmetical graphs, introduced by Lorenzini, viewing them as a class of vertex weighted graphs whose Laplacian is orthogonal to a positive vector and describe how they may be viewed as a special class of unweighted strongly connected directed graphs.
For the entire collection see [Zbl 1242.05003].

05C20 Directed graphs (digraphs), tournaments
05C10 Planar graphs; geometric and topological aspects of graph theory
05C57 Games on graphs (graph-theoretic aspects)
Full Text: Link arXiv
[1] O. Amini and M. Manjunath. Riemann-Roch for sub-lattice of the root lattice. Preprint. · Zbl 1277.05105
[2] Asadi, A.; Backman, S.: Chip-firing and Riemann-Roch theory for arithmetical graphs. (2010)
[3] Baker, M.; Norine, S.: Riemann-Roch theorem and Abel-Jacobi theory on a finite graph. Advances in mathematics 215, 766-788 (2007) · Zbl 1124.05049
[4] Bollobás, B.: Modern graph theory. (1998) · Zbl 0902.05016
[5] Dhar, D.: Self-organized critical state of sandpile automaton models. Phys. rev. Lett. 64, No. 14, 1613-1616 (1990) · Zbl 0943.82553
[6] Holroyd, A. E.; Levine, L.; Mszros, K.; Peres, Y.; Propp, J.; Wilson, D. B.: Chip-firing and rotor-routing on directed graphs. Progress in probability 60, 331-364 (2008) · Zbl 1173.82339
[7] Lorenzini, D.: Frobenius number, Riemann-Roch structure and zeta functions · Zbl 1286.14036
[8] Lorenzini, D.: Arithmetical graphs. Mathematische annalen 285, 481-501 (1989) · Zbl 0662.14008
[9] Speer, E. R.: Asymmetric abelian sandpile models. J. stat. Phys. 71, 61-74 (1993) · Zbl 0943.82551
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.