On the gonality of Kneser graphs — Draconitic Research

Abstract

The Kneser graphs KG(n,k) are a classically studied family of graphs. One known invariant of graphs is gonality (also called divisorial gonality), which is the minimum degree of a rank 1 divisor on the graph. Using known bounds on gonality of simple, connected graphs, one may obtain that the gonality of KG(n,k) is bounded above by binomn−1k. In 2014, Harvey and Wood showed that the treewidth (a lower bound on gonality) for KG(n,k) is binomn−1k−1 for n≥ 4k²−3k+2. In this paper, using scramble number, another lower bound on gonality, we improve this polynomial bound and show that the gonality of KG(n,k) is exactly binomn−1k for n≥ (3k²+k+2)/2, and conjecture an even stricter polynomial bound using the uniform edge scramble. We then extend our argument to the family of generalized Kneser Graphs, computing the scramble number and gonality using the same polynomial bound.

Endomorphisms of Total Kneser Graphs
Esmaeil Alhaj Mostafa Abdan, Jacob Russell, Sophia Ulvestad
arXiv2 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematics Geometry & topologyarXiv
The Genus of Bipartite Kneser Graphs
Austin Ulrigg, Alexander Metzger
arXiv2 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
The rational homology of independence complexes of Kneser graphs on triples
Ziqin Feng
arXiv12 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics Geometry & topologyarXiv
The chromatic number of G-stable Kneser graphs
Carmen Arana, Penny Haxell, Tomáš Kaiser +1
arXiv13 Oct 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Improved Solution–Function Inequalities and Kneser-Type Oscillation Criteria for Noncanonical Neutral Differential Equations with Continuous Delay
Osama Moaaz, Asma Al-Jaser
Axioms27 Oct 2026Peer-reviewedCC BY 4.0General mathematicsCrossref

Cite

BibTeX RIS

BibTeX

@misc{ballinas2026gonality,
  title = {{On the gonality of Kneser graphs}},
  author = {Luis A. Ballinas and Willoughby Caine and D. Blake Hopkins and Doel Rivera Laboy},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.00258},
  eprint = {2609.00258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.00258},
}

RIS

TY  - UNPB
TI  - On the gonality of Kneser graphs
AU  - Luis A. Ballinas
AU  - Willoughby Caine
AU  - D. Blake Hopkins
AU  - Doel Rivera Laboy
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.00258
UR  - https://arxiv.org/abs/2609.00258
AB  - The Kneser graphs KG(n,k) are a classically studied family of graphs. One known invariant of graphs is gonality (also called divisorial gonality), which is the minimum degree of a rank 1 divisor on the graph. Using known bounds on gonality of simple, connected graphs, one may obtain that the gonality of KG(n,k) is bounded above by binomn−1k. In 2014, Harvey and Wood showed that the treewidth (a lower bound on gonality) for KG(n,k) is binomn−1k−1 for n≥ 4k^2−3k+2. In this paper, using scramble number, another lower bound on gonality, we improve this polynomial bound and show that the gonality of KG(n,k) is exactly binomn−1k for n≥ (3k^2+k+2)/2, and conjecture an even stricter polynomial bound using the uniform edge scramble. We then extend our argument to the family of generalized Kneser Graphs, computing the scramble number and gonality using the same polynomial bound.
ER  -

Abstract

Related

Cite