← All problems

Unit-gap conjecture for diameters of Schrijver graphs

5 years old · traced to

Let kk and rr be integers with 2≤r≤k−22\leq r\leq k-2, and let D(G)D(G) denote the diameter of a graph GG. For n=2k+rn=2k+r, write SG⁡(n,k)\operatorname{SG}(n,k) for the Schrijver graph. Unit-gap conjecture. If 2≤r≤k−22\leq r\leq k-2, then

D(SG⁡(2k+r,k))−D(SG⁡(2k+r+1,k))∈0,1.D\left(\operatorname{SG}(2k+r,k)\right)-D\left(\operatorname{SG}(2k+r+1,k)\right)\in\\{0,1\\}.

The conjecture concerns the possibility of larger drops in the diameter as rr increases. It is based on computations and is open; the paper notes that the analogous differences are in 0,1\\{0,1\\} for k≤5k\leq 5, while a larger gap occurs at the transition from r=1r=1 to r=2r=2 when k≥6k\geq 6.

References
  1. Agustina Victoria Ledezma, Adrián Pastine, Pablo Torres and Mario Valencia-Pabon, “On the diameter of Schrijver graphs”, arXiv:2112.01884 (2022).

Progress summary

Refreshed
Open · progress reported

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 rr cannot reduce the diameter by more than one in the stated range.

Known results

  • Exact diameter formulas are proved for r=1r=1, r=2r=2, and r≥k−3r\geq k-3 (Ledezma, Pastine, Torres, and Valencia-Pabon, 2021).
  • Bounds are given for 3≤r≤k−43\leq r\leq k-4 (Ledezma, Pastine, Torres, and Valencia-Pabon, 2021).
  • Computations support the conjectured differences for k≤5k\leq 5; a larger drop occurs from r=1r=1 to r=2r=2 when k≥6k\geq 6, outside the conjecture’s range.

November 2026 claimed counterexample

A submission dated November 7, 2026 argues that D(SG⁡(27,12))≥8D(\operatorname{SG}(27,12))\geq 8 while D(SG⁡(28,12))≤6D(\operatorname{SG}(28,12))\leq 6, producing a drop of 22 at k=12k=12, r=3r=3. 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 k=12k=12, r=3r=3 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 solutionHide 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.