Metraipolis › archive › dc_356f8f69e4be
On the gonality of Kneser graphs — arXiv:2609.00258
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.00258
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T07:06:19.915Z
- SHA-256 of the archived text
8f5110500067c99e7cfdd01122acd9a68d4f4f124c146a2c3e4378215c96d6b4- Stable URL of this page
https://metraipolis.com/documento/dc_356f8f69e4be
How to cite
On the gonality of Kneser graphs — arXiv:2609.00258 — arXiv (en), https://arxiv.org/abs/2609.00258 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_356f8f69e4be (Metraipolis archive dc_356f8f69e4be, sha256 8f5110500067c99e7cfdd01122acd9a68d4f4f124c146a2c3e4378215c96d6b4)
BibTeX
@misc{dc356f8f69e4be,
title = {On the gonality of Kneser graphs — arXiv:2609.00258},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.00258},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_356f8f69e4be; sha256 8f5110500067c99e7cfdd01122acd9a68d4f4f124c146a2c3e4378215c96d6b4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.00258. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Kneser graphs $\text{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 $\text{KG}(n,k)$ is bounded above by $\binom{n-1}{k}$. In 2014, Harvey and Wood showed that the treewidth (a lower bound on gonality) for $\text{KG}(n,k)$ is $\binom{n-1}{k}-1$ for $n\geq 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 $\text{KG}(n,k)$ is exactly $\binom{n-1}{k}$ for $n\geq \frac{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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-02 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.00258 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T06:52:59.675Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).