Riemann-Roch theory for graph orientations

DOI10.1016/J.AIM.2017.01.005zbMATH Open1355.05140arXiv1401.3309OpenAlexW2964022551MaRDI QIDQ509688FDOQ509688

Authors: Spencer Backman 

Publication date: 17 February 2017

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

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.

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

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

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)

Cites Work

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

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
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• On the gonality of Cartesian products of graphs
• Combinatorics of compactified universal Jacobians
• Kasteleyn cokernels and perfect matchings on planar bipartite graphs
• Generalized Riemann functions, their weights, and the complete graph
• Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem
• A Riemann-Roch theorem for hypermaps
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Compactified Jacobians as Mumford models
• On metric graphs with prescribed gonality
• A Riemann-Roch Theorem on Infinite Graphs
• Fourientations and the Tutte polynomial
• 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)