Divisorial gonality of graphs, the slice rank polynomial method, and tensor products of convex cones
J. van Dobben de Bruyn (TU Delft - Discrete Mathematics and Optimization)
D.C. Gijswijt – Promotor (TU Delft - Discrete Mathematics and Optimization)
O.W. van Gaans – Copromotor (Universiteit Leiden)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This dissertation explores three interconnected topics at the interface of combinatorics, algebra, and geometry.
In Part I, we study the divisorial gonality of graphs, a graph parameter inspired by algebraic geometry. Introduced by Baker around 2007, divisorial gonality links chip-firing games on graphs to classical algebraic geometry, including the combinatorial Riemann–Roch theorem and Brill–Noether theory. We contribute in two ways. First, we provide a constructive proof that treewidth is a lower bound for divisorial gonality, presenting a polynomial-time algorithm that transforms a positive rank effective divisor into a tree decomposition of bounded width. This bridges gonality with structural graph theory and enables dynamic programming techniques for graphs of bounded gonality. Second, we examine the Brill–Noether conjecture for graphs and disprove Baker’s subdivision conjecture by constructing graphs whose gonality exceeds that of the associated metric graphs. While the Brill–Noether existence conjecture remains unresolved, our results clarify structural limitations in approaching its proof.
Part II investigates applications of the slice rank polynomial method to affine configurations over finite fields. Extending the method initially developed to solve the cap set problem, we analyze subsets of
Fqn
F
q
n
avoiding non-trivial solutions to systems of balanced linear equations. For certain classes of systems, we demonstrate the existence of solutions with pairwise distinct or maximally affinely independent elements, generalizing previous results by Mimura and Tokushige. These findings contribute to understanding the limitations and potential of slice rank techniques for broader combinatorial problems.
In Part III, we study tensor products of convex cones, a topic relevant across functional analysis, operator theory, approximation theory, and theoretical physics. Existing literature mainly addresses Archimedean lattice cones or finite-dimensional proper generating cones, leaving many cones unexamined. We extend known results to general cones and present several new contributions: we establish mapping properties for projective/injective cones analogous to norms, characterize their lineality spaces and extremal rays, show containment of projective/injective tensor products in proper cones, and demonstrate that tensoring symmetric convex sets preserves proper faces. For closed cones in finite-dimensional spaces, we show that the projective cone is closed and almost always strictly contained in the injective cone, partially recovering Barker’s conjecture prior to its independent full proof by Aubrun et al. Our work unifies tensor product properties across a wide class of convex cones and provides new tools for both theoretical and applied analysis.
Together, these three parts demonstrate the deep interplay between combinatorics, algebra, and geometry, advancing understanding in graph theory, finite field combinatorics, and convex analysis. The results provide constructive algorithms, generalized theoretical frameworks, and novel counterexamples, opening directions for further research in structural graph theory, algebraic combinatorics, and tensor analysis.