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