IsExpandable
A 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 set Y disjoint from X with |Y| ≤ 2r, there is an edge of H containing X and disjoint from Y.
Statement
def IsExpandable {V : Type*} (H : Finset (Finset V)) (r : ℕ) (X : Finset V) : Prop
- Defined in
- arXiv:2611.16957, Definition 3.2
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Used by 3
- 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…
- edge_is_expandableEvery nonempty edge in a hypergraph where all edges have size at most r is expandable.
- card_le_of_is_expandableEvery expandable set in a hypergraph with edge size bound r has cardinality at most r.
Read back from the Lean
Given a type V, a finite collection H of finite subsets of V (a hypergraph), a natural number r, and a finite subset X of V, IsExpandable H r X holds if and only if all of the following hold:
1. X is nonempty;
2. every element e ∈ H has cardinality at most r (|e| ≤ r); and
3. for every finite subset Y of V, if Y is disjoint from X and |Y| ≤ 2 * r, then there exists some e ∈ H such that X ⊆ e and e is disjoint from Y.
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
/-- A nonempty set X is expandable in hypergraph H with bound r if every edge in H has size at most r and every disjoint set Y of size at most 2r can be avoided by an edge containing X. -/ def IsExpandable {V : Type*} (H : Finset (Finset V)) (r : ℕ) (X : Finset V) : Prop := X.Nonempty ∧ (∀ e ∈ H, e.card ≤ r) ∧ ∀ Y : Finset V, Disjoint Y X → Y.card ≤ 2 * r → ∃ e ∈ H, X ⊆ e ∧ Disjoint e Y