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
- finset_one_inclusion_graph_not_adj_empty_pairIn the one-inclusion graph of {∅, {a, b}} with a ≠ b, ∅ and {a, b} are not adjacent.
- finset_one_inclusion_graph_adj_empty_singletonIn the one-inclusion graph of {∅, {a}}, ∅ and {a} are adjacent.
- finset_one_inclusion_graph_card_edgeFinset_leIf a finite set system F has VC dimension at most d, its one-inclusion graph has at most d·|F| edges.
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⟩