Divisorial gonality of graphs, the slice rank polynomial method, and tensor products of convex cones

On the size of subsets of Fⁿ_q avoiding solutions to linear systems with repeated columns

Consider a system of m balanced linear equations in k variables with coefficients in F_q. If k ⩾ 2m + 1, then a routine application of the slice rank method shows that there are constants β, γ ⩾ 1 with γ < q such that, for every subset S ⊆ Fⁿq of size at least β · γⁿ, the system has a solution (x₁...

Almost all positive continuous linear functionals can be extended

Let F be an ordered topological vector space (over R) whose positive cone F₊ is weakly closed, and let E⊆ F be a subspace. We prove that the set of positive continuous linear functionals on E that can be extended (positively and continuously) to F is weak-∗ dense in the topological dual wedge E+′. Furthermore, we show that this...

Discrete and metric divisorial gonality can be different

This paper compares the divisorial gonality of a finite graph G to the divisorial gonality of the associated metric graph Γ(G,1) with unit lengths. We show that dgon(Γ(G,1)) is equal to the minimal divisorial gonality of all regular subdivisions of G, and we provide a class of graphs for which this number is strictly smaller than the...

Constructing tree decompositions of graphs with bounded gonality

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related...

Constructing tree decompositions of graphs with bounded gonality

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related...

Treewidth is a lower bound on graph gonality

We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. Graphs for which equality holds include the grid graphs and the complete multipartite graphs. We prove that the treewidth lower bound also holds for metric graphs (tropical curves) by constructing for any positive rank divisor on a metric...