Infinite reduction of divisors on metric graphs

DOI10.1016/J.EJC.2013.06.024MaRDI QIDQ2509736zbMATH OpenOpenAlexFDO

Authors Spencer Backman

Publication date 29 July 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We demonstrate that the greedy algorithm for reduction of divisors on metric graphs need not terminate by modeling the Euclidean algorithm in this context. We observe that any infinite reduction has a well defined limit allowing us to treat the greedy reduction algorithm as a transfinite algorithm and to analyze its running time via ordinal numbers. We provide lower and upper bounds which establish a worst case running time of $omeg{a}^{Theta(mdeg(D))}$.

Recommendations

• Rank-determining sets of metric graphs
• Rank of divisors on tropical curves
• Effective divisor classes on metric graphs
• Computing linear systems on metric graphs
• Algebraic and combinatorial rank of divisors on finite graphs

Cites work

• A Riemann-Roch theorem in tropical geometry
• A tropical proof of the Brill-Noether theorem
• Chip-firing games, potential theory on graphs, and spanning trees
• scientific article; zbMATH DE number 1314876 (Why is no real title available?)
• Linear systems on tropical curves
• Metrized graphs, Laplacian operators, and electrical networks
• Rank of divisors on tropical curves
• Rank-determining sets of metric graphs
• Reduced divisors and embeddings of tropical curves
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Tropical curves, their Jacobians and theta functions

Cited in

(2)

• Generators of invariant linear system on tropical curves for finite isometry group
• Degeneration of linear series from the tropical point of view and applications

This page was built for publication: Infinite reduction of divisors on metric graphs

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