Chip-firing and Riemann-Roch theory for directed graphs

zbMATH Open1274.05189arXiv1012.0287MaRDI QIDQ2857320FDOQ2857320

Authors: Arash Asadi, Spencer Backman 

Publication date: 1 November 2013

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.

Full work available at URL: https://arxiv.org/abs/1012.0287

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

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)

Cites Work

• Title not available (Why is that?)
• Riemann-Roch for sub-lattices of the root lattice \(A_n\)
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Two-variable zeta-functions on graphs and Riemann-Roch theorems
• Self-organized critical state of sandpile automaton models
• Arithmetical graphs
• Chip-Firing and Rotor-Routing on Directed Graphs
• Asymmetric Abelian sandpile models

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)