Enumerating linear systems on graphs
- PDF / 960,248 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 6 Downloads / 201 Views
Mathematische Zeitschrift
Enumerating linear systems on graphs Sarah Brauner1 · Forrest Glebe2 · David Perkinson3 Received: 1 August 2019 / Accepted: 10 December 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
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. Our results also apply to a model in which the Laplacian is replaced by an invertible, integral M-matrix. Keywords Divisor theory of graphs · Complete linear system · Chip-firing · Graph Laplacian · Binary necklaces · M-matrix Mathematics Subject Classification Primary 05C30; Secondary 05C25
1 Introduction Let G be a finite, connected, undirected graph with vertex set V . The divisor theory of graphs uses the graph Laplacian to view G as a discrete analogue of a Riemann surface. As a reference, the reader should consult the seminal paper by Baker and Norine [3], a main result of which is the Riemann-Roch theorem for graphs. That work is related to a broader circle
B
Sarah Brauner [email protected] Forrest Glebe [email protected] David Perkinson [email protected]
1
University of Minnesota, Minneapolis, MN, USA
2
Purdue University, West Lafayette, IN, USA
3
Reed College, Portland, OR, USA
123
S. Brauner et al.
of ideas that includes chip-firing on graphs [7], the arithmetical groups of Lorenzini [17], the abelian sandpile model [2,9], and parking functions in combinatorics [22]. For general textbooks, including many references, see [8] and [16]. The papers [15] and [1] are also recommended. Precise definitions follow in Sect. 2, but for the purposes of this introduction, it is useful to think of divisor theory on graphs in terms of the dollar game introduced in [3]. By definition, a divisor D is an element of ZV , the free abelian group on the vertices of G. Think of D as an assignment of D(v) dollars to each vertex v. If the integer D(v) is negative, then v is in debt. The net amount of money on the graph is the degree, deg(D) := v∈V D(v), of D. A lending move (or firing) by a vertex v consists of v giving one dollar to each of its neighbors and losing the corresponding amount itself. A borrowing move is the opposite, in which v takes a dollar from each of its neighbors. Two divisors are linearly eq
Data Loading...
