AFTD Auto-Formalizing Theoretical Domains

finset_one_inclusion_graph

def

The one-inclusion graph G_1(F) of a set system F: its vertices are the members of F, two members adjacent when their symmetric difference has exactly one element.

Statement

def finset_one_inclusion_graph {α : Type*} [DecidableEq α] (𝓕 : Finset (Finset α)) :
    SimpleGraph 𝓕
Defined in
arXiv:2610.08151 (Polynomial-in-r bounds for forbidden traces of uniform hypergraphs), Sec. 2.2 (one-inclusion graph G_1(F), before Lemma 2). Vertices are the members of 𝓕 (a subtype).
Verified
11 Oct 2026
Axioms
none listed
Used by 3

Lean source view module on GitHub

/-- The one-inclusion graph of a set system: its members are the vertices, and two members are adjacent when their symmetric difference has exactly one element. -/
def finset_one_inclusion_graph {α : Type*} [DecidableEq α] (𝓕 : Finset (Finset α)) :
    SimpleGraph 𝓕 where
  Adj A B := (symmDiff (A : Finset α) B).card = 1
  symm := ⟨fun A B (h : (symmDiff (A : Finset α) B).card = 1) => by rwa [symmDiff_comm]⟩
  loopless := ⟨fun A (h : (symmDiff (A : Finset α) A).card = 1) => by simp at h⟩
See it in the graphDiscuss this resultChallenge it