AFTD Auto-Formalizing Theoretical Domains

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

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⟩
}
See it in the graphDiscuss this resultChallenge it