card_le_of_is_expandable
Every expandable set in a hypergraph with edge size bound r has cardinality at most r.
Statement
theorem card_le_of_is_expandable {V : Type*} {H : Finset (Finset V)} {r : ℕ} {X : Finset V} (hX : IsExpandable H r X) : X.card ≤ r
- Source
- arXiv:2611.16957, Section 3.1
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- IsExpandableA nonempty set X of vertices is expandable in a hypergraph H with edge size bound r if every edge of H has size at most r, and for every…
- Used by 1
- no_loose_triangle_of_expandable_setsLet H be a hypergraph (a finite collection of finite subsets of V) and let r be a natural number. If H contains no loose triangle (for all…
Read back from the Lean
For any type V, finite set of finite subsets H of V, natural number r, and finite subset X of V, if X is expandable with respect to H and r (IsExpandable H r X), then the cardinality of X is at most r.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
By the definition of an expandable set, any set disjoint from X of size at most 2r avoids an edge containing X. Specializing this to the empty set yields an edge e ∈ H containing X. Since all hyperedges in H have cardinality at most r, the subset relation implies |X| ≤ |e| ≤ r.
There exists a hyperedge e ∈ H containing X.
By the definition of an expandable set, any set Y disjoint from X with |Y| ≤ 2r avoids some edge e ∈ H that contains X. Specializing this condition to Y = ∅, which is disjoint from X by Finset.disjoint_empty_left and has cardinality 0 ≤ 2r, yields an edge e ∈ H with X ⊆ e.
uses
Finset.disjoint_empty_leftobtain ⟨e, heH, hXe, -⟩ := hX.2.2 ∅ (Finset.disjoint_empty_left X) (by simp)
|X| ≤ r
Because X ⊆ e, Finset.card_le_card gives |X| ≤ |e|. The definition of expandability also specifies that every edge in H has cardinality at most r, so |e| ≤ r. Combining these inequalities with le_trans gives |X| ≤ r.
uses
Finset.card_le_card,le_transexact le_trans (Finset.card_le_card hXe) (hX.2.1 e heH)
Finset.disjoint_empty_left- The empty set is disjoint from any finite set.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
le_trans- If a ≤ b and b ≤ c in a preorder, then a ≤ c.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- An expandable set in a hypergraph with edge size bound r has cardinality at most r. -/theorem card_le_of_is_expandable {V : Type*} {H : Finset (Finset V)} {r : ℕ} {X : Finset V} (hX : IsExpandable H r X) : X.card ≤ r := by obtain ⟨e, heH, hXe, -⟩ := hX.2.2 ∅ (Finset.disjoint_empty_left X) (by simp) exact le_trans (Finset.card_le_card hXe) (hX.2.1 e heH)