AFTD Auto-Formalizing Theoretical Domains

edge_is_expandable

theoremverified

Every nonempty edge in a hypergraph where all edges have size at most r is expandable.

Statement

theorem edge_is_expandable {V : Type*} {H : Finset (Finset V)} {r : ℕ} {e : Finset V} (he : e ∈ H) (hne : e.Nonempty) (hr : ∀ f ∈ H, f.card ≤ r) : IsExpandable H r e
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…

Read back from the Lean

Let V be a type, H a finite collection of finite subsets of V, r a natural number, and e a finite subset of V. Assume that: 1. e ∈ H, 2. e is nonempty, and 3. every member f ∈ H has cardinality at most r. Then e is expandable with respect to H and r (IsExpandable H r e).

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

To show that a nonempty edge $e \in H$ is expandable, we must verify that $e$ is nonempty, that all edges in $H$ have size at most $r$, and that any set $Y$ disjoint from $e$ with size at most $2r$ avoids some edge containing $e$. The first two conditions hold immediately by assumption. For the extension condition, $e$ itself serves as the required edge: it belongs to $H$, contains itself, and is disjoint from $Y$ by symmetry.

  1. $e$ is expandable in $H$ with bound $r$ (`IsExpandable H r e`).

    By definition, $e$ is expandable in $H$ with bound $r$ if $e$ is nonempty, all edges in $H$ have cardinality at most $r$, and for any set $Y$ disjoint from $e$ with $|Y| \le 2r$, there exists an edge $f \in H$ containing $e$ that is disjoint from $Y$. The first two conditions are supplied directly by the hypotheses `hne` ($e \ne \emptyset$) and `hr` ($\forall f \in H, |f| \le r$). For the third condition, given $Y$ disjoint from $e$ (hypothesis `hdisj`), the edge $e$ itself serves as the witness: $e \in H$ by `he`, $e \subseteq e$ by reflexivity of inclusion (`subset_rfl`), and $e$ is disjoint from $Y$ by symmetry of disjointness (`hdisj.symm`).

    line 3

    uses subset_rfl

      refine ⟨hne, hr, fun Y hdisj _ => ⟨e, he, subset_rfl, hdisj.symm⟩⟩
subset_rfl
Every set is a subset of itself ($a \subseteq a$).

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

/-- Every nonempty edge of a hypergraph with edge sizes at most r is expandable. -/theorem edge_is_expandable {V : Type*} {H : Finset (Finset V)} {r : ℕ} {e : Finset V} (he : e ∈ H) (hne : e.Nonempty) (hr : ∀ f ∈ H, f.card ≤ r) : IsExpandable H r e := by  refine ⟨hne, hr, fun Y hdisj _ => ⟨e, he, subset_rfl, hdisj.symm⟩⟩
See it in the graphDiscuss this resultChallenge it