Séminaire Lotharingien de Combinatoire, 82B.17 (2019), 12 pp.
Sarah Brauner, Forrest Glebe, and David Perkinson
Enumerating linear systems on graphs
Abstract.
The divisor theory of graphs views a finite connected graph G as a discrete version of a Riemann surface. Divisors on G are formal integral combinations of the vertices of G, and linear equivalence of divisors is determined by the discrete Laplacian operator for G. As in the case of Riemann surfaces, we are interested in the complete linear system |D| of a divisor D - the collection of nonnegative divisors linearly equivalent to D. Unlike the case of Riemann surfaces, the complete linear system of a divisor on a graph is always finite. We compute generating functions encoding the sizes of all complete linear systems on G. We interpret our results in terms of polyhedra associated with divisors and in terms of the invariant theory of the (dual of the) Jacobian group of G. If G is a cycle graph, our results lead to a bijection between complete linear systems and binary necklaces.
Received: November 15, 2018.
Accepted: February 17, 2019.
Final version: April 1, 2019.
The following versions are available: