Back to Search
Start Over
Enumerating linear systems on graphs
- Publication Year :
- 2019
-
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$ and 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. The final section generalizes our results to a model based on integral $M$-matrices.<br />Comment: 26 pages; added "Further work" section
- Subjects :
- Mathematics - Combinatorics
05C30, 05C25
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1906.04768
- Document Type :
- Working Paper