Chip-Firing and Riemann-Roch Theory for Directed Graphs

2010/12/01 by Arash Asadi, Asadi, Arash, Spencer Backman +1 · 1 citation
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #math-ph #math.CO #math.MP

paper · pdf · doi:10.48550/arxiv.1012.0287

arxiv created 2011/09/23 · arxiv updated 2011/09/26

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₀-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 G-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.

Cited by

• Generalized chip firing and critical groups of arithmetical structures on trees

Related

• Riemann-Roch for Toric Rank Functions
• The Riemann-Roch theorem for graphs and the rank in complete graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Chip-firing game and partial Tutte polynomial for Eulerian digraphs
• Periods and atomic firing sequences of parallel chip-firing games on directed graphs