Unit-gap conjecture for diameters of Schrijver graphs
Let and be integers with , and let denote the diameter of a graph . For , write for the Schrijver graph. Unit-gap conjecture. If , then
The conjecture concerns the possibility of larger drops in the diameter as increases. It is based on computations and is open; the paper notes that the analogous differences are in for , while a larger gap occurs at the transition from to when .
References
- Agustina Victoria Ledezma, Adrián Pastine, Pablo Torres and Mario Valencia-Pabon, “On the diameter of Schrijver graphs”, arXiv:2112.01884 (2022).
Progress summary
A reader-submitted argument claims a counterexample in 2026, but the conjecture remains unverified and publicly unsettled.
Ledezma, Pastine, Torres, and Valencia-Pabon proposed the unit-gap conjecture in their 2021 study of Schrijver-graph diameters. It asserts that increasing the parameter cannot reduce the diameter by more than one in the stated range.
Known results
- Exact diameter formulas are proved for , , and (Ledezma, Pastine, Torres, and Valencia-Pabon, 2021).
- Bounds are given for (Ledezma, Pastine, Torres, and Valencia-Pabon, 2021).
- Computations support the conjectured differences for ; a larger drop occurs from to when , outside the conjecture’s range.
November 2026 claimed counterexample
A submission dated November 7, 2026 argues that while , producing a drop of at , . This would refute the conjecture, but the argument is unverified.
Current status (as of November 2026): The classical partial results and computational evidence remain established, while the claimed , counterexample is unverified.
Sources
Solutions 1
Stable Kneser graphs violate the unit-gap diameter conjecture: D(SG(27,12)) ≥ 8 while D(SG(28,12)) ≤ 6See full solution
Result and scope. Ledezma, Pastine, Torres, Valencia-Pabon, arXiv:2112.01884v2 (DAM 350 (2024) 15-30), Conjecture 2. False at k = 12, r = 3: D(SG(27,12)) ≥ 8 by an explicit pair (masks 21669205, 39144021) with a distance-labelling certificate, and D(SG(28,12)) ≤ 6 by BFS-tree certificates over 116 rotation-orbit representatives; the drop is 2. Independent of the source's Theorem 6 (found false; the r = 2 route was a source-internal correction and is not credited).
Complete proof: Stable Kneser graphs violate the unit-gap diameter conjecture: D(SG(27,12)) ≥ 8 while D(SG(28,12)) ≤ 6 · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.