generalized_kneser_graph_adj
In the generalized Kneser graph KG(2n, n, r), two vertices s and t are adjacent if and only if s ≠ t and the cardinality of their intersection s.1 ∩ t.1 is strictly less than r.
Statement
theorem generalized_kneser_graph_adj (n r : ℕ)
(s t : {s : Finset (Fin (2 * n)) // s.card = n}) :
(generalized_kneser_graph n r).Adj s t ↔ s ≠ t ∧ (s.1 ∩ t.1).card < r- Source
- arXiv:2611.04486 Sec. 1
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- generalized_kneser_graphThe generalized Kneser graph KG(2n, n, r) is the simple graph whose vertices are the n-element subsets of Fin (2 * n), where two distinct…
- Used by 1
- generalized_kneser_chromatic_le_fourteenFor every natural number n ≥ 4, the chromatic number of the generalized Kneser graph KG(2n, n, 3) is at most 14.
Read back from the Lean
For all natural numbers n and r, and all vertices s and t (which are n-element subsets of Fin (2 * n)), s and t are adjacent in generalized_kneser_graph n r if and only if s ≠ t and the cardinality of the intersection s ∩ t is strictly less than r.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
In the definition of the generalized Kneser graph KG(2n, n, r), two vertices s and t are defined to be adjacent if and only if s ≠ t and |s ∩ t| < r. Since the left-hand and right-hand sides of the equivalence are definitionally equal, the statement holds immediately by reflexivity of equivalence.
The adjacency condition in the generalized Kneser graph is definitionally equal to s ≠ t ∧ |s ∩ t| < r.
By definition of `generalized_kneser_graph`, the adjacency relation `(generalized_kneser_graph n r).Adj s t` is defined directly as `s ≠ t ∧ (s.1 ∩ t.1).card < r`. Because both sides of the `↔` are definitionally identical, the equivalence holds by reflexivity (`Iff.rfl`).
uses
Iff.rfl(generalized_kneser_graph n r).Adj s t ↔ s ≠ t ∧ (s.1 ∩ t.1).card < r := Iff.rfl
Iff.rfl- Every proposition is equivalent to itself (P ↔ P).
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Adjacency criterion for the generalized Kneser graph KG(2n, n, r). -/theorem generalized_kneser_graph_adj (n r : ℕ) (s t : {s : Finset (Fin (2 * n)) // s.card = n}) : (generalized_kneser_graph n r).Adj s t ↔ s ≠ t ∧ (s.1 ∩ t.1).card < r := Iff.rfl