generalized_kneser_graph
def
The 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 subsets s and t are adjacent if and only if the cardinality of their intersection s ∩ t is strictly less than r.
Statement
def generalized_kneser_graph (n r : ℕ) :
SimpleGraph {s : Finset (Fin (2 * n)) // s.card = n}- Defined in
- arXiv:2611.04486 Sec. 1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 3
- 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.
- card_generalized_kneser_graph_vertsThe vertex type of the generalized Kneser graph KG(2n, n, r), which consists of all n-element subsets of Fin (2 * n), has cardinality…
- generalized_kneser_graph_adjIn 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…
Read back from the Lean
For natural numbers n and r, generalized_kneser_graph n r is the simple graph whose vertices are the n-element subsets of Fin (2 * n) (that is, {s : Finset (Fin (2 * n)) // s.card = n}), where 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.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The generalized Kneser graph KG(2n, n, r) whose vertices are n-element subsets of a (2n)-element ground set, adjacent when their intersection size is strictly less than r. -/ def generalized_kneser_graph (n r : ℕ) : SimpleGraph {s : Finset (Fin (2 * n)) // s.card = n} := { Adj := fun s t => s ≠ t ∧ (s.1 ∩ t.1).card < r symm := ⟨fun s t h => ⟨h.1.symm, by rw [Finset.inter_comm]; exact h.2⟩⟩ loopless := ⟨fun s h => h.1 rfl⟩ }