Chip-firing and Riemann-Roch theory for directed graphs

MaRDI QIDQ2857320zbMATH OpenFDO

Authors Arash Asadi, Spencer Backman

Publication date 1 November 2013

Full work available at URL https://arxiv.org/abs/1012.0287, http://www.sciencedirect.com/science/article/pii/S1571065311000801

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: We investigate Riemann-Roch theory for directed graphs. The Riemann-Roch criteria of Amini and Manjunath is generalized to all integer lattices orthogonal to some positive vector. Using generalized notions of a $v_0$-reduced divisor and Dhar's algorithm we investigate two chip-firing games coming from the rows and columns of the Laplacian of a strongly connected directed graph. We discuss how the "column" chip-firing game is related to directed $vecG$-parking functions and the "row" chip-firing game is related to the sandpile model. We conclude with a discussion of arithmetical graphs, which after a simple transformation may be viewed as a special class of directed graphs which will always have the Riemann-Roch property for the column chip-firing game. Examples of arithmetical graphs are provided which demonstrate that either, both, or neither of the two Riemann-Roch conditions may be satisfied for the row chip-firing game.

Recommendations

• Chip-firing based methods in the Riemann-Roch theory of directed graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Chip firing and algebraic curves
• Chip-firing games on directed graphs
• Simplicial dollar game

Cites work

• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Arithmetical graphs
• Asymmetric Abelian sandpile models
• Chip-Firing and Rotor-Routing on Directed Graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• Self-organized critical state of sandpile automaton models
• Two-variable zeta-functions on graphs and Riemann-Roch theorems

Cited in

(17)

• Multi-Eulerian tours of directed graphs
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• Minimal free resolutions of lattice ideals of digraphs
• Chip firing on Dynkin diagrams and McKay quivers
• Arithmetical structures on bidents
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Parking functions on nonsingular \(M\)-matrices
• Explicit deformation of lattice ideals via chip-firing games on directed graphs
• A maximizing characteristic for critical configurations of chip-firing games on digraphs
• Monomials, binomials and Riemann-Roch
• Chip-firing and energy minimization on M-matrices
• Parallel chip-firing on the complete graph: Devil’s staircase and Poincaré rotation number
• CoEulerian graphs
• A chip-firing game on the product of two graphs and the tropical Picard group
• Abelian networks IV. Dynamics of nonhalting networks
• Chip-firing based methods in the Riemann-Roch theory of directed graphs
• Chip-firing games and critical groups

This page was built for publication: Chip-firing and Riemann-Roch theory for directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2857320)