Gonality Sequences and Divisor Rank on Graphs

16 concepts3 papers1 proposal

In the study of graph theory, the concept of gonality offers a way to measure the complexity of a graph by looking at the behavior of "divisors"—collections of chips placed on the graph's vertices. Drawing from analogies in algebraic geometry, researchers use these divisors to understand how easily one can move chips around a graph to reach specific configurations.

The Budget of Flexibility

To understand gonality, imagine a game played on a graph where you place a certain number of chips on the vertices. A divisor is simply this arrangement of chips. Through a process called "chip-firing," you can move these chips along edges according to specific rules.

The rank of a divisor describes its flexibility: a divisor has rank at least $r$ if, no matter which $r$ vertices an opponent chooses, you can fire your chips to ensure at least one chip lands on each of those chosen vertices. The gonality of a graph, denoted $\text{gon}(G)$, is the minimum number of chips (the minimum degree) required to achieve a rank of at least 1. In other words, it is the smallest budget of chips that allows you to reach any single vertex on the graph.

From Single Values to Sequences

While the first gonality provides a baseline for graph complexity, it does not capture the full picture. Aidun et al. introduced the gonality sequence, an ordered list of values $\gamma_r(G)$ representing the minimum number of chips needed to achieve rank $r$ for increasing values of $r$.

This sequence acts as a more granular invariant than a single number. For instance, Aidun et al. demonstrated that for graphs with a low genus (up to genus 5), the entire gonality sequence is uniquely determined by just two factors: the graph's genus and its first gonality. This suggests that for simpler graphs, the "cost" of increasing the rank follows a predictable pattern tied to the graph's topological complexity.

Structural Constraints and Treewidth

The gonality of a graph is often constrained by its underlying structure. A common point of comparison is treewidth, a measure of how closely a graph resembles a tree. In many cases, gonality and treewidth are closely linked, but specific families of graphs reveal where these measures diverge.

Aidun et al. explored this relationship by computing the gonality of "glued grid graphs," such as toroidal grids and stacked prisms. By constructing "brambles"—dense collections of connected subgraphs—the authors established tight bounds on these parameters. Their work shows that while gonality generally scales with the dimensions of the grid, certain configurations (like specific toroidal families) present unique challenges that prevent a simple one-to-one mapping between treewidth and gonality.

The Multiplicity Constraint

In the standard definition of gonality, you can stack as many chips as you like on a single vertex. However, Dean et al. introduced a variation called multiplicity-free gonality ($\text{mf-gon}(G)$). In this version, each vertex is restricted to holding at most one chip.

This restriction fundamentally changes the difficulty of the problem. The authors proved that:

  • Equality is Rare: For simple graphs, multiplicity-free gonality only equals traditional gonality for trees (where both are 1) and cycles (where both are 2).
  • Divergence: For more complex graphs, the multiplicity-free version can be significantly larger than the standard version.
  • Complexity: Determining the multiplicity-free gonality is NP-hard, and for some graphs, it may not even be possible to achieve a rank of 1 under this constraint, making the value infinite.

By comparing these different measures—the sequence of ranks, the structural bounds of grids, and the impact of chip placement constraints—researchers are building a comprehensive map of how discrete geometry and graph topology interact.

Key Foundational Work

Gonality Sequences of Graphs (2021) — contributed 12 concept elements to this direction.
Treewidth and gonality of glued grid graphs (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_divisor_degree_sequence_49b66a55,
  title = {divisor degree sequence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/divisor-degree-sequence/rdr_49b66a55fbe942bb84598e57f06ae674},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_divisor_degree_sequence_49b66a55_v1,
  title = {divisor degree sequence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/divisor-degree-sequence/rdr_49b66a55fbe942bb84598e57f06ae674/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake