Gonality sequences of graphs

DOI10.1137/20M1323072MaRDI QIDQ4986811zbMATH OpenFDO

Authors Ivan Aidun, Frances Dean, Ralph Morrison, Teresa Yu, Julie Yuan

Publication date 28 April 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graphchip-firinggonality sequenceDhar's burning algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of tropical varieties (14T15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Games on graphs (graph-theoretic aspects) (05C57) Special divisors on curves (gonality, Brill-Noether theory) (14H51)

Abstract: To any graph we associate a sequence of integers called the gonality sequence of the graph, consisting of the minimum degrees of divisors of increasing rank on the graph. This is a tropical analogue of the gonality sequence of an algebraic curve. We study gonality sequences for graphs of low genus, proving that for genus up to $5$, the gonality sequence is determined by the genus and the first gonality. We then prove that any reasonable pair of first two gonalities is achieved by some graph. We also develop a modified version of Dhar's burning algorithm more suited for studying higher gonalities.

Recommendations

• The gonality sequence of complete graphs
• Gonality of algebraic curves and graphs
• Sparse graphs of high gonality
• On metric graphs with prescribed gonality
• Treewidth is a lower bound on graph gonality

Cites work

• scientific article; zbMATH DE number 13051 (Why is no real title available?)
• scientific article; zbMATH DE number 1455876 (Why is no real title available?)
• A Riemann-Roch theorem in tropical geometry
• A combinatorial Li-Yau inequality and rational points on curves
• A note on Brill-Noether existence for graphs of low genus
• A note on Brill-Noether theory and rank-determining sets for metric graphs
• A tropical proof of the Brill-Noether theorem
• Brill-Noether theory of curves on \( \mathbb{P}^1 \times \mathbb{P}^1\): tropical and classical approaches
• Chip-firing games, potential theory on graphs, and spanning trees
• Clifford Indices for Vector Bundles on Curves
• Clifford's theorem for graphs
• Computing graph gonality is hard
• Divisors and sandpiles. An introduction to chip-firing
• Gonality of random graphs
• Graphs of gonality three
• Harmonic Morphisms and Hyperelliptic Graphs
• Linear pencils encoded in the Newton polygon
• Newton polygons and curve gonalities
• Polynomial Bound for a Chip Firing Game on Graphs
• Rank of divisors on tropical curves
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• Self-organized critical state of sandpile automaton models
• Specialization of linear systems from curves to graphs (with an appendix by Brian Conrad)
• The gonality sequence of complete graphs
• The lattice size of a lattice polygon
• Tropical curves, their Jacobians and theta functions
• Tropical hyperelliptic curves

Cited in

(15)

• Sparse graphs of high gonality
• On the gonality of Cartesian products of graphs
• On the gonality of graphs and connections to orientable genus
• On the semigroup of graph gonality sequences
• Gonality of expander graphs
• On an exact sequence related to a graph
• Gonality of algebraic curves and graphs
• Brill-Noether theory of curves on \( \mathbb{P}^1 \times \mathbb{P}^1\): tropical and classical approaches
• Multiplicity-free gonality on graphs
• On the scramble number of graphs
• Gonality of random graphs
• Catalan-many tropical morphisms to trees. Part I: Constructions
• Graphs of gonality three
• Vertex sequences in graphs
• The gonality sequence of complete graphs

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Gonality sequences of graphs

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