Brill–Noether existence on graphs via ${\mathbb {R}}$-divisors, polytopes and lattices

Abstract

We study Brill–Noether existence on a finite graph using methods from polyhedral geometry and lattices. We start by formulating analogues of the Brill–Noether conjectures (both the existence and non-existence parts) for ${\mathbb {R}}$-divisors, i.e. divisors with real coefficients, on a graph. We then reformulate the Brill–Noether existence conjecture for ${\mathbb {R}}$-divisors on a graph in geometric terms, that we refer to as the covering radius conjecture and we show a weak version, in support of it. Using this, we show an approximate version of the Brill–Noether existence conjecture for divisors on a graph. As applications, we derive upper bounds on the gonality of a graph and its ${\mathbb {R}}$-divisor analogue.

Riemann–Roch theory for \({\mathbb {R}}\)-divisors on a graph

We elaborate on [2, Section 8.1] and state a Riemann–Roch theorem for ${\mathbb {R}}$-divisors on a graph. This is a special case, in a slightly different language, of the Riemann–Roch theorem for edge-weighted graphs due to James and Miranda [20] with each edge weight equal to the number of multiedges between the corresponding pair of vertices.

Let G be an undirected, connected multigraph, with no loops, having n vertices, m edges and genus g. Following [2], we define the sigma region of G as follows:

Definition A.1

The sigma region ${\tilde{\Sigma }}^c(G)$ is the closure (under the Euclidean topology) of the subset of $\mathrm{Div}_{{\mathbb {R}}}(G)$ consisting of all ${\mathbb {R}}$-divisors D whose modified rank ${\tilde{r}}(D)$ is equal to $-1$.

The set ${\tilde{\Sigma }}^c(G)$ relates to the set $\Sigma ^c(G)$ introduced just after [2, Definition 2.3] as ${\tilde{\Sigma }}^c(G)=-\Sigma ^c(G)$, this follows from their definitions. Let $\widetilde{\mathrm{Ext}}^c(G)$ be the set of local maxima of the degree function restricted to ${\tilde{\Sigma }}^c(G)$. By [2, Item i, Theorem 6.9], the set $\widetilde{\mathrm{Ext}}^c(G)$ is equal to ${\mathcal {N}}_G+\sum _v (v)$ where ${\mathcal {N}}_G$ is the set of non-special divisors on G. Recall that, by definition, ${\mathcal {N}}_G$ is the set of divisors of degree $g-1$ and rank minus one. The following characterisation of the sigma region is the key to the Riemann–Roch theorem:

Proposition A.2

An ${\mathbb {R}}$-divisor D is contained in the sigma region if and only if there exists an element ${\tilde{\nu }} \in \widetilde{\mathrm{Ext}}^c(G)$ such that ${\tilde{\nu }}-D$ is an effective ${\mathbb {R}}$-divisor.

Proposition A.2 is a generalisation of [2, Theorem 2.6] to ${\mathbb {R}}$-divisors. This leads to the following formula for the modified rank of an ${\mathbb {R}}$-divisor:

Proposition A.3

The modified rank ${\tilde{r}}(D)$ of an ${\mathbb {R}}$-divisor on G is equal to

$$\begin{aligned} \mathrm{min}_{{\tilde{\nu }} \in \widetilde{\mathrm{Ext}}^c(G)}\mathrm{deg^{+}}(D-{\tilde{\nu }})-1. \end{aligned}$$

Proposition A.3 is a generalisation of [2, Lemma 2.9] to ${\mathbb {R}}$-divisors. However, note the changes in sign in both these generalisations (Propositions A.2 and A.3) that arise from the difference between ${\tilde{\Sigma }}^c(G)$ and $\Sigma ^c(G)$. As a corollary, we deduce the continuity of the modified rank function ${\tilde{r}}$.

Corollary A.4

The modified rank ${{\tilde{r}}}: \mathrm{Div}_{{\mathbb {R}}}(G) \rightarrow {\mathbb {R}}$ is a continuous function where $\mathrm{Div}_{{\mathbb {R}}}(G)$ is identified with the real vector space of rank n equipped with the Euclidean topology.

The following analogue of the Riemann–Roch theorem follows from Proposition A.3,

Theorem A.5

(Riemann–Roch for ${\mathbb {R}}$-Divisors: Version 1) Let $\tilde{K_G}=\sum _v \mathrm{val}(v)(v)$ where $\mathrm{val}(v)$ is the valency of the vertex v. Let $g_{{\mathbb {R}}}=m+1$, where m is the number of edges of G. For any ${\mathbb {R}}$-divisor D, the following formula holds:

$$\begin{aligned} {\tilde{r}}(D)-{\tilde{r}}(\tilde{K_G}-D)=\mathrm{deg}(D)-(g_{{\mathbb {R}}}-1). \end{aligned}$$

The modified rank ${\tilde{r}}$ is related to the Baker-Norine rank r(D) in the case where $D \in \mathrm{Div_{{\mathbb {Z}}}}(G)$ as ${\tilde{r}}(D+\sum _v (v))=r(D)$. Note that the rank $r:\mathrm{Div}_{{\mathbb {R}}}(G) \rightarrow {\mathbb {R}}$ is $r(D):={\tilde{r}}(D+\sum _v (v))=\mathrm{min}_{\nu \in {\mathcal {N}}_G}\mathrm{deg^{+}}(D-\nu )-1$ (cf. Proposition 2.5). Substituting $D+\sum _{v} (v)$ in Theorem A.5 gives the following version.

Theorem A.6

(Riemann–Roch for ${\mathbb {R}}$-Divisors: Version 2). Let $K_G=\sum _v (\mathrm{val}(v)-2)(v)$ where v is the valency of the vertex v and let g be the genus of G. For any ${\mathbb {R}}$-divisor D, the following formula holds:

$$\begin{aligned} r(D)-r(K_G-D)=\mathrm{deg}(D)-(g-1). \end{aligned}$$

The proofs of these statements are along the same lines as the proofs of the Riemann–Roch theorem for graphs in [8] and [2].

Remark A.7

We point out some properties (and related subtleties) of the rank function r (in its extension to ${\mathbb {R}}$-divisors).

• 1. As in the case of divisors, the rank of an effective ${\mathbb {R}}$-divisor $E_{{\mathbb {R}}}$ is non-negative. This follows from the observation that any element in ${\mathcal {N}}_G$ is a divisor with rank minus one. Hence, for any element in ${\mathcal {N}}_G$ there is a vertex where it has coefficient at most minus one. We then apply the degree plus formula (Proposition 2.5) to conclude that $r(E_{{\mathbb {R}}}) \ge 0$. A similar argument also shows that an ${\mathbb {R}}$-divisor of the form $r_0 \cdot (1,\ldots ,1)$ for a non-negative real number $r_0$ has rank at least $r_0$.

• 2. Unlike in the case of divisors, the rank of an ${\mathbb {R}}$-divisor of negative degree need not be negative. As an example, consider a tree on n vertices where $n \ge 5$ is an odd integer. In this case, the set ${\mathcal {N}}_G$ is the set of all divisors of degree minus one. The subset of ${\mathcal {N}}_G$ that realises the rank of the divisor zero (in the degree plus formula) is precisely $\{-e_i|~$for i from one to n where $e_i$ is the i-th standard basis vector of ${\mathbb {R}}^n\}$. By the discreteness of ${\mathcal {N}}_G$, the same set also realises the rank of the ${\mathbb {R}}$-divisor $D_{{\mathbb {R}}}=\sum _{i=1}^{(n-1)/2} \epsilon \cdot e_i-\sum _{i=(n+1)/2}^{n} \epsilon \cdot e_i$ for sufficiently small $\epsilon >0$. Its degree is $-\epsilon <0$ and its rank is $(n-3)/2 \cdot \epsilon >0$ (since $n \ge 5$). By Riemann–Roch, this also implies that $K_G-D_{{\mathbb {R}}}$ has degree strictly greater than $2g-2$ and rank strictly greater than its degree minus g. This is also in contrast with the case of divisors.

• 3. The modified rank function ${\tilde{r}}$, however, behaves similar to the case of divisors in this respect: ${\mathbb {R}}$-divisors of negative degree have negative modified rank and ${\mathbb {R}}$-divisors of degree d strictly greater than $2g_{{\mathbb {R}}}-2$ have modified rank $d-g_{{\mathbb {R}}}$. This implies that ${\mathbb {R}}$-divisors of degree strictly less than $-n$ have negative rank and ${\mathbb {R}}$-divisors of degree d strictly greater than $2g-2+n$ have rank equal to $d-g$.

• 4. There are ${\mathbb {R}}$-divisors of degree zero that are not principal and have positive rank: consider a tree on n vertices where n is even, the ${\mathbb {R}}$-divisor $\sum _{i=1}^{n/2} \epsilon \cdot e_i-\sum _{i=n/2+1}^{n} \epsilon \cdot e_i$ for sufficiently small $\epsilon >0$ has degree zero but is not principal and has positive rank by an argument similar to that in Item 2. $\square$