Enumerating linear systems on graphs (Q5918971)

Let \(G=(V,E)\) be a finite connected undirected graph. The divisor theory of graphs uses the graph Laplacian to view \(G\) as a discrete analogue of a Riemann surface. A divisor \(D\) is an element of \(\mathbb{Z}V\), the free abelian group on the vertices of \(G\). Here, \[\mathrm{Div}(G):=\mathbb{Z}V=\left\{\sum\limits_{v\in V}D(v)v:D(v)\in \mathbb{Z}\right\}.\] The complete linear system of a divisor \(D\), denoted \(|D|\), is the set of all effective divisors linearly equivalent to \(D\). The purpose of this paper is to answer the question: What is the cardinality of the complete linear system \(|D|\) for each divisor \(D\)? Let the Laplacian operator of \(G\) be the function \(L : \mathbb{Z}^V \rightarrow \mathbb{Z}^V\) given by \[L(f)(v)=\sum\limits_{vw\in E(G)}(f(v)-f(w))\] for each \(f\in \mathbb{Z}^V\) and \(v\in V\). Then the divisor of a function \(f: V \rightarrow \mathbb{Z}\), arising by analogy from the theory of divisors on Riemann surfaces, is \[\mathrm{div}(f):=\sum\limits_{v\in V}(L(f)(v))v\in\mathrm{Div}(G).\] Divisors of functions are called principal divisors, and they form an additive subgroup of Div\((G)\) denoted Prin\((G)\). Two divisors \(D\) and \(D'\) are linearly equivalent if \(D-D\in\mathrm{Prin}(G)\). The Picard group of \(G\) is then the group of divisors modulo linear equivalence: \[\mathrm{Pic}(G) := \mathrm{Div}(G)/ \mathrm{Prin}(G).\] The degree-zero part of the Picard group is a subgroup called the Jacobian group of \(G\): \[\mathrm{Jac}(G):=\mathrm{Pic}^0(G) = \mathrm{Div}^0(G)/ \mathrm{Prin}(G).\] Let \([D]\) denote the class of a divisor \(D\) modulo Prin\((G)\). With respect to a fixed vertex \(q\), there is an isomorphism from Pic\((G)\) to \(Z \oplus \mathrm{Jac}(G)\), which is applied to partition the collection of all effective divisors on \(G\) into sets. The \(\lambda\)-sequence for \([D]\in\mathrm{Jac}(G)\) is the sequence with \(k\)-th term \[\lambda_{[D]}(k):=\#|D+kq|.\] The generating function for the \(\lambda\)-sequence is \[\Lambda_{[D]}(z):=\sum\limits_{k\ge 0}\Lambda_{[D]}(k)z^k.\] The authors prove that each effective divisor has a decomposition into a sum of primary and secondary divisors for \(G\). Then they compute a rational expression for \(\Lambda_{[D]}(z)\) for each \([D]\in\mathrm{Jac}(G)\). They reinterpret the results in terms of lattice points in a rational polyhedra cone. Generators for the cone correspond to primary divisors and lattice points in a fundamental parallelepiped correspond to secondary divisors; the rational expression for \(\Lambda_{[D]}(z)\) is re-derived using standard lattice-point counting techniques. They approach the question using invariant theory and apply results to the specific case of the cycle graph \(C_n\), yielding a remarkable connection to binary necklaces. Moreover, they generalize the work to \(M\)-matrices. They show how each \(M\)-matrix gives rise to a family of matrices -- each serving the role of the Laplacian matrix and allowing results to be extended to this broader context. As examples, they discuss two particular cases: Cartan matrices for crystallographic root systems and McKay-Cartan matrices for faithful complex representations of arbitrary finite groups.