Riemann-Roch theory for graph orientations

DOI10.1016/J.AIM.2017.01.005MaRDI QIDQ509688zbMATH OpenOpenAlexFDO

Authors Spencer Backman

Publication date 17 February 2017

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

chip-firingcycle-cocycle reversal systemDhar's algorithmMAX-flow MIN-cut theorempartial graph orientationrank-determining setRiemann-Roch theorem for graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Families, moduli of curves (analytic) (14H15)

Abstract: We develop a new framework for investigating linear equivalence of divisors on graphs using a generalization of Gioan's cycle--cocycle reversal system for partial orientations. An oriented version of Dhar's burning algorithm is introduced and employed in the study of acyclicity for partial orientations. We then show that the Baker--Norine rank of a partially orientable divisor is one less than the minimum number of directed paths which need to be reversed in the generalized cycle--cocycle reversal system to produce an acyclic partial orientation. These results are applied in providing new proofs of the Riemann--Roch theorem for graphs as well as Luo's topological characterization of rank-determining sets. We prove that the max-flow min-cut theorem is equivalent to the Euler characteristic description of orientable divisors and extend this characterization to the setting of partial orientations. Furthermore, we demonstrate that $Pi{c}^{g-1}(G)$ is canonically isomorphic as a $Pi{c}^0(G)$-torsor to the equivalence classes of full orientations in the cycle--cocycle reversal system acted on by directed path reversals. Efficient algorithms for computing break divisors and constructing partial orientations are presented.

Recommendations

• Chip-firing based methods in the Riemann-Roch theory of directed graphs
• Riemann-Roch theory on finite sets
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• A Riemann-Roch theorem in tropical geometry
• Riemann-Roch theory for weighted graphs and tropical curves

Cites work

• scientific article; zbMATH DE number 3411070 (Why is no real title available?)
• A Riemann-Roch theorem in tropical geometry
• Activity preserving bijections between spanning trees and orientations in graphs
• Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem
• Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
• Chip-firing games on graphs
• Chip-firing games, potential theory on graphs, and spanning trees
• Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
• Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
• Lattice structures from planar graphs
• Maximal Flow Through a Network
• On the History of Combinatorial Optimization (Till 1960)
• On the degrees of the vertices of a directed graph
• Packing directed circuits
• Permutohedra, Associahedra, and Beyond
• Polynomial ideals for sandpiles and their Gröbner bases
• Rank-determining sets of metric 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
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• The polytope of win vectors
• The sand-pile model and Tutte polynomials
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Tropical curves, their Jacobians and theta functions
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
• \(G\)-parking functions, acyclic orientations and spanning trees

Cited in

(27)

• Generalized Riemann functions, their weights, and the complete graph
• A Riemann-Roch Theorem on Infinite Graphs
• Fourientations and the Tutte polynomial
• Combinatorics of compactified universal Jacobians
• Compactified Jacobians as Mumford models
• Tutte short exact sequences of graphs
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem
• Geometric bijections between spanning trees and break divisors
• A Riemann-Roch type theorem for twisted fibrations of moment graphs
• On the number of circuit-cocircuit reversal classes of an oriented matroid
• Degeneration of linear series from the tropical point of view and applications
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Chip-firing based methods in the Riemann-Roch theory of directed graphs
• Partial graph orientations and the Tutte polynomial
• A Riemann-Roch theorem for hypermaps
• On computation of Baker and Norine's rank on complete graphs
• Divisors on graphs, orientations, syzygies, and system reliability
• Effective divisor classes on metric graphs
• Trimming the permutahedron to extend the parking space
• Kasteleyn cokernels and perfect matchings on planar bipartite graphs
• Multiplicity-free gonality on graphs
• On the gonality of Cartesian products of graphs
• A Torelli theorem for graph isomorphisms
• On the scramble number of graphs
• Geometric bijections between spanning subgraphs and orientations of a graph
• On metric graphs with prescribed gonality

This page was built for publication: Riemann-Roch theory for graph orientations

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