AFTD Auto-Formalizing Theoretical Domains

kneser_compl

def

The complement of the Kneser graph K(n, k) is the simple graph whose vertices are the k-element subsets of Fin n, with an edge between two distinct subsets if and only if they are not disjoint (they have nonempty intersection).

Statement

def kneser_compl (n k : ℕ) : SimpleGraph {s : Finset (Fin n) // s.card = k}
Defined in
arXiv:2611.17183, Section 3
Verified
14 Nov 2026
Axioms
none listed

Read back from the Lean

For natural numbers n and k, kneser_compl n k is the simple graph whose vertices are the subsets (of type Finset (Fin n)) of Fin n having cardinality k, where two vertices s and t are adjacent if and only if s ≠ t and s.val and t.val are not disjoint (i.e., they have non-empty intersection).

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 complement of the Kneser graph K(n, k) on k-element subsets of Fin n. -/
def kneser_compl (n k : ℕ) : SimpleGraph {s : Finset (Fin n) // s.card = k} where
  Adj s t := s ≠ t ∧ ¬ Disjoint s.1 t.1
  symm := ⟨fun _ _ h => ⟨h.1.symm, fun hd => h.2 hd.symm⟩⟩
  loopless := ⟨fun _ h => h.1 rfl⟩
See it in the graphDiscuss this resultChallenge it