AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_graph

def

For integers k ≥ 2 and r ≥ 0, G(k,r) is the bipartite graph on two disjoint copies of the family of k-element subsets of {1, ..., 2k-1}, where two vertices a_S and b_T are adjacent if and only if |S ∩ T| ≤ r.

Statement

def bipartite_subset_graph (k r : ℕ) :
    SimpleGraph ({S : Finset (Fin (2 * k - 1)) // S.card = k} ⊕ {T : Finset (Fin (2 * k - 1)) // T.card = k})
Defined in
arXiv:2610.42094, Definition 1.2
Verified
03 Nov 2026
Axioms
none listed
Used by 6

Read back from the Lean

bipartite_subset_graph k r is the simple graph whose vertices are the disjoint union of two copies of {S : Finset (Fin (2 * k - 1)) // S.card = k} (the $k$-element subsets of Fin (2 * k - 1)). An edge exists between a vertex Sum.inl S in the first copy and a vertex Sum.inr T in the second copy if and only if the cardinality of their intersection is at most r ((S.1 ∩ T.1).card ≤ r). There are no edges between two vertices belonging to the same copy.

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 bipartite subset graph G(k,r) whose two vertex classes are copies of the k-subsets of 2k-1, adjacent when their intersection has size at most r. -/
def bipartite_subset_graph (k r : ℕ) :
    SimpleGraph ({S : Finset (Fin (2 * k - 1)) // S.card = k} ⊕ {T : Finset (Fin (2 * k - 1)) // T.card = k}) := {
  Adj := fun
    | Sum.inl S, Sum.inr T => (S.1 ∩ T.1).card ≤ r
    | Sum.inr T, Sum.inl S => (S.1 ∩ T.1).card ≤ r
    | _, _ => False
  symm := ⟨by
    intro u v h
    cases u <;> cases v <;> simp at h ⊢ <;> exact h⟩
  loopless := ⟨by
    intro u
    cases u <;> simp⟩
}
See it in the graphDiscuss this resultChallenge it