Brill-Noether existence on graphs via \(\mathbb{R}\)-divisors, polytopes and lattices (Q2071744)

This paper concerns the Brill-Noether existence problem for \(\mathbb{R}\)-divisors on graphs. Brill-Noether theory for graphs builds up starting from the analogies between the combinatorial aspects of finite graphs with the ones of compact Riemann surfaces developed in several works, as the work by \textit{M. Baker} and \textit{S. Norine} [Adv. Math. 215, No. 2, 766--788 (2007; Zbl 1124.05049)] and the one by \textit{M. Baker} [Algebra Number Theory 2, No. 6, 613--653 (2008; Zbl 1162.14018)]. The main goal of Brill-Noether theory is to classify divisors of given degree \(d\) and rank \(r\) on the objects of interest, which in this case are undirected connected loop-free multigraphs with \(n\geq2\) vertices, \(m\) edges and genus \(g=m-n+1\geq1\). Let \(\rho(g,r,d)=g-(r+1)(g-d+r)\); the core of Brill-Noether theory deals with divisors of degree \(0\leq d\leq 2g-2\), and the main question, which is also the starting point of this work, is Conjecture 3.9 of Baker [loc. cit.], which states that given a graph \(G\) of genus \(g\), for \((r,d)\) such that \(d\leq 2g-2\), if \(\rho(g,r,d)\geq 0\) there exists a divisor \(D\) of degree at most \(d\) and rank \(r\) on \(G\). This conjecture is open except for graphs of genus at most 5, for which \textit{S. Atanasov} and \textit{D. Ranganathan} in [Mich. Math. J. 67, No. 1, 175--198 (2018; Zbl 1420.14134)] give a positive answer, and also construct families of graphs with increasing genus where existence conjecture works in rank one. The autor of this work restates the Brill-Noether existence conjecture for \(\mathbb{R}\)-divisors on graphs and then shows that it is equivalent to his covering radius conjecture. Let \(\mathcal{N}_G\) be the set of non-special divisors over a graph \(G\): we can see it as a subset of the hyperplane \(H_{g-1}=\{(x_1,\dots,x_n)\in \mathbb{R}^n\mid \sum_{i=1}^nx_i=g-1 \}\). The conjecture is the following: Let \(\lambda\in[1/g,g]\), the covering radius of \(\mathcal{N}_G\) with respect to the polytope \(P_{1,\lambda}\) is at least \(\sqrt{g/{\lambda}}/n\), with \(P_{1,\lambda}\) being a polytope defined for each \(\lambda.\) This conjecture is open. The first main result of this work shows a weaker version of this conjecture implying Brill-Noether existence for dense multigraphs., i.e. graphs with \(m\geq n(n-1)\). The proof is attained using the equivalence of the conjectures above, and then showing that the covering radius conjecture holds for the particular case of dense graphs. From this result, the author develops some bounds for the gonality of dense graphs. The other two main results deal again with Brill-Noether existence conjecture. The first is an approximate version of the Brill-Noether existence, namely the author proves existence of an \((r_0,d_0)\)-divisor for an undirected, connected, multigraph with stretch factor \(k:=\max(\lceil(n(n-1))/m\rceil,1)\) satisfying \(\tilde{\rho}(g,r_0,d_0)=g-k(r_0+1)(g-d_0+r_0)\geq 0\). The second is a weaker version of the existence for complete graphs, namely \(K_n\) on \(n\geq 3\) vertices has a divisor of degree \(g-1\) and rank at least \(\sqrt{g}/4-1\) and if \(n\) is odd then it has a divisor of degree \(g-1 \) and rank at least \(\sqrt{g}\sqrt{2}-1\).