no_loose_triangle_of_expandable_sets
Let 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 edges e₁, e₂, e₃ in H, they do not form a loose triangle), then no three sets X₁, X₂, X₃ that are expandable in H with parameter r form a loose triangle.
Statement
theorem no_loose_triangle_of_expandable_sets {V : Type*} [DecidableEq V] (H : Finset (Finset V)) (r : ℕ) (h_no_lt : ∀ e₁ ∈ H, ∀ e₂ ∈ H, ∀ e₃ ∈ H, ¬ is_loose_triangle e₁ e₂ e₃) (X₁ X₂ X₃ : Finset V) (hX₁ : IsExpandable H r X₁) (hX₂ : IsExpandable H r X₂) (hX₃ : IsExpandable H r X₃) : ¬ is_loose_triangle X₁ X₂ X₃
- Formalizes
- arXiv:2611.16957 Lemma 3.3 -- Ramsey numbers of loose triangles versus cliques
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- is_loose_triangleThree edges e₁, e₂, e₃ in a hypergraph form a loose triangle if they are pairwise distinct, each pair intersects in exactly one vertex,…
- 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
Let $V$ be a type with decidable equality. Let $H$ be a finite set of finite subsets of $V$ (a hypergraph on $V$) and let $r \in \mathbb{N}$. Suppose that no three edges $e_1, e_2, e_3 \in H$ form a loose triangle (that is, for all $e_1, e_2, e_3 \in H$, $\neg \operatorname{is\_loose\_triangle}(e_1, e_2, e_3)$). Let $X_1, X_2, X_3$ be finite subsets of $V$. If $X_1$, $X_2$, and $X_3$ are each expandable with respect to $H$ and $r$ ($\operatorname{IsExpandable}(H, r, X_i)$ for each $i \in \{1, 2, 3\}$), then $X_1, X_2, X_3$ do not form a loose triangle ($\neg \operatorname{is\_loose\_triangle}(X_1, X_2, X_3)$).
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
The proof argues by contradiction. Assuming three expandable sets X₁, X₂, X₃ form a loose triangle, we sequentially expand each set Xᵢ to a hyperedge eᵢ ∈ H avoiding the union of the other sets and already constructed edges. A helper lemma ensures that these expansions preserve the pairwise intersections of the original sets without introducing any new common vertices. Consequently, the hyperedges e₁, e₂, e₃ are pairwise distinct and their intersection structure matches that of X₁, X₂, X₃, forming a loose triangle in H and contradicting the hypothesis that H contains no loose triangles.
If A ⊆ S, B ⊆ T, and S is disjoint from T \ A, then S ∩ B = A ∩ B.
To establish set equality, we show both inclusions for an arbitrary element x. If x ∈ A ∩ B, then x ∈ S ∩ B directly because A ⊆ S. Conversely, if x ∈ S ∩ B, then x ∈ S and x ∈ B ⊆ T. If x ∉ A, then x ∈ T \ A, which contradicts the assumption that S and T \ A are disjoint. Hence x ∈ A, which gives x ∈ A ∩ B.
uses
Finset.mem_inter,Finset.disjoint_left.mp,Finset.mem_sdiff.mprext x simp only [Finset.mem_inter] constructor · rintro ⟨hxS, hxB⟩ by_cases hxA : x ∈ A · exact ⟨hxA, hxB⟩ · exfalso exact (Finset.disjoint_left.mp hdisj) hxS (Finset.mem_sdiff.mpr ⟨hBT hxB, hxA⟩) · rintro ⟨hxA, hxB⟩ exact ⟨hA hxA, hxB⟩
Supposing for contradiction that X₁, X₂, X₃ form a loose triangle, we extract their intersection sizes and unpack their expandability properties.
We assume for contradiction that X₁, X₂, X₃ form a loose triangle. Unfolding the definition gives that the sets are pairwise distinct, each pairwise intersection has cardinality 1 (|X₁ ∩ X₂| = |X₂ ∩ X₃| = |X₃ ∩ X₁| = 1), and the intersection of X₁ ∩ X₂ with X₃ is empty. By card_le_of_is_expandable, the expandable sets X₂ and X₃ each have cardinality at most r. Furthermore, unpacking the expandability hypotheses yields that every edge in H has cardinality at most r, and that any set disjoint from Xᵢ of size at most 2 * r can be avoided by some edge in H containing Xᵢ.
uses
is_loose_triangle,card_le_of_is_expandableintro hlt rw [is_loose_triangle] at hlt obtain ⟨_, _, _, hc12, hc23, hc13, hdisjX⟩ := hlt have hX₂card : X₂.card ≤ r := card_le_of_is_expandable hX₂ have hX₃card : X₃.card ≤ r := card_le_of_is_expandable hX₃ obtain ⟨_, hbnd₁, hexp₁⟩ := hX₁ obtain ⟨_, hbnd₂, hexp₂⟩ := hX₂ obtain ⟨_, hbnd₃, hexp₃⟩ := hX₃
There is an edge e₁ ∈ H containing X₁ that is disjoint from (X₂ ∪ X₃) \ X₁, with |e₁| ≤ r.
The set difference Y₁ = (X₂ ∪ X₃) \ X₁ is disjoint from X₁ by construction, and its cardinality is at most |X₂ ∪ X₃| ≤ |X₂| + |X₃| ≤ 2 * r. Applying the expandability of X₁ to Y₁ gives an edge e₁ ∈ H containing X₁ and disjoint from Y₁. Since e₁ ∈ H, its cardinality is at most r.
uses
Finset.card_le_card,Finset.sdiff_subset,Finset.card_union_le,Finset.disjoint_sdiff.symmhave hY₁card : ((X₂ ∪ X₃) \ X₁).card ≤ 2 * r := by have h1 := Finset.card_le_card (Finset.sdiff_subset : (X₂ ∪ X₃) \ X₁ ⊆ X₂ ∪ X₃) have h2 := Finset.card_union_le X₂ X₃ omega obtain ⟨e₁, he₁H, hX₁sube₁, hdisj₁⟩ := hexp₁ ((X₂ ∪ X₃) \ X₁) Finset.disjoint_sdiff.symm hY₁card have he₁card : e₁.card ≤ r := hbnd₁ e₁ he₁H
There is an edge e₂ ∈ H containing X₂ that is disjoint from (e₁ ∪ X₃) \ X₂, with |e₂| ≤ r.
The set Y₂ = (e₁ ∪ X₃) \ X₂ is disjoint from X₂, and its cardinality satisfies |Y₂| ≤ |e₁ ∪ X₃| ≤ |e₁| + |X₃| ≤ 2 * r because |e₁| ≤ r and |X₃| ≤ r. Applying expandability of X₂ to Y₂ yields an edge e₂ ∈ H containing X₂ and disjoint from Y₂, with |e₂| ≤ r.
uses
Finset.card_le_card,Finset.sdiff_subset,Finset.card_union_le,Finset.disjoint_sdiff.symmhave hY₂card : ((e₁ ∪ X₃) \ X₂).card ≤ 2 * r := by have h1 := Finset.card_le_card (Finset.sdiff_subset : (e₁ ∪ X₃) \ X₂ ⊆ e₁ ∪ X₃) have h2 := Finset.card_union_le e₁ X₃ omega obtain ⟨e₂, he₂H, hX₂sube₂, hdisj₂⟩ := hexp₂ ((e₁ ∪ X₃) \ X₂) Finset.disjoint_sdiff.symm hY₂card have he₂card : e₂.card ≤ r := hbnd₂ e₂ he₂H
There is an edge e₃ ∈ H containing X₃ that is disjoint from (e₁ ∪ e₂) \ X₃.
The set Y₃ = (e₁ ∪ e₂) \ X₃ is disjoint from X₃, and its cardinality satisfies |Y₃| ≤ |e₁ ∪ e₂| ≤ |e₁| + |e₂| ≤ 2 * r because both e₁ and e₂ have cardinality at most r. Applying expandability of X₃ to Y₃ yields an edge e₃ ∈ H containing X₃ and disjoint from Y₃.
uses
Finset.card_le_card,Finset.sdiff_subset,Finset.card_union_le,Finset.disjoint_sdiff.symmhave hY₃card : ((e₁ ∪ e₂) \ X₃).card ≤ 2 * r := by have h1 := Finset.card_le_card (Finset.sdiff_subset : (e₁ ∪ e₂) \ X₃ ⊆ e₁ ∪ e₂) have h2 := Finset.card_union_le e₁ e₂ omega obtain ⟨e₃, he₃H, hX₃sube₃, hdisj₃⟩ := hexp₃ ((e₁ ∪ e₂) \ X₃) Finset.disjoint_sdiff.symm hY₃card
The intersections of the edges with the sets satisfy e₁ ∩ X₂ = X₁ ∩ X₂, e₁ ∩ X₃ = X₁ ∩ X₃, e₂ ∩ e₁ = X₂ ∩ e₁, e₂ ∩ X₃ = X₂ ∩ X₃, e₃ ∩ e₁ = X₃ ∩ e₁, and e₃ ∩ e₂ = X₃ ∩ e₂.
Each equality follows from the helper lemma no_loose_triangle_of_expandable_sets_inter. For e₁, since X₁ ⊆ e₁ and e₁ is disjoint from (X₂ ∪ X₃) \ X₁, intersecting e₁ with X₂ ⊆ X₂ ∪ X₃ and X₃ ⊆ X₂ ∪ X₃ yields X₁ ∩ X₂ and X₁ ∩ X₃ respectively. The other four equalities follow symmetrically for e₂ and e₃ with their respective avoided unions.
uses
no_loose_triangle_of_expandable_sets_inter,Finset.subset_union_left,Finset.subset_union_righthave hA1 : e₁ ∩ X₂ = X₁ ∩ X₂ := no_loose_triangle_of_expandable_sets_inter hX₁sube₁ hdisj₁ Finset.subset_union_left have hA2 : e₁ ∩ X₃ = X₁ ∩ X₃ := no_loose_triangle_of_expandable_sets_inter hX₁sube₁ hdisj₁ Finset.subset_union_right have hB1 : e₂ ∩ e₁ = X₂ ∩ e₁ := no_loose_triangle_of_expandable_sets_inter hX₂sube₂ hdisj₂ Finset.subset_union_left have hB2 : e₂ ∩ X₃ = X₂ ∩ X₃ := no_loose_triangle_of_expandable_sets_inter hX₂sube₂ hdisj₂ Finset.subset_union_right have hC1 : e₃ ∩ e₁ = X₃ ∩ e₁ := no_loose_triangle_of_expandable_sets_inter hX₃sube₃ hdisj₃ Finset.subset_union_left have hC2 : e₃ ∩ e₂ = X₃ ∩ e₂ := no_loose_triangle_of_expandable_sets_inter hX₃sube₃ hdisj₃ Finset.subset_union_right
The pairwise intersections of the edges satisfy e₁ ∩ e₂ = X₁ ∩ X₂, e₂ ∩ e₃ = X₂ ∩ X₃, and e₁ ∩ e₃ = X₁ ∩ X₃, and each has cardinality 1.
Using commutativity of intersection and the equalities from the previous step, e₁ ∩ e₂ = e₂ ∩ e₁ = X₂ ∩ e₁ = e₁ ∩ X₂ = X₁ ∩ X₂. Identical rewrites show e₂ ∩ e₃ = X₂ ∩ X₃ and e₁ ∩ e₃ = X₁ ∩ X₃. Since the pairwise intersections of X₁, X₂, X₃ each have cardinality 1, the pairwise intersections e₁ ∩ e₂, e₂ ∩ e₃, and e₃ ∩ e₁ each have cardinality 1.
uses
Finset.inter_commhave h12eq : e₁ ∩ e₂ = X₁ ∩ X₂ := by rw [Finset.inter_comm e₁ e₂, hB1, Finset.inter_comm X₂ e₁, hA1] have h23eq : e₂ ∩ e₃ = X₂ ∩ X₃ := by rw [Finset.inter_comm e₂ e₃, hC2, Finset.inter_comm X₃ e₂, hB2] have h13eq : e₁ ∩ e₃ = X₁ ∩ X₃ := by rw [Finset.inter_comm e₁ e₃, hC1, Finset.inter_comm X₃ e₁, hA2] have hcard12 : (e₁ ∩ e₂).card = 1 := by rw [h12eq]; exact hc12 have hcard23 : (e₂ ∩ e₃).card = 1 := by rw [h23eq]; exact hc23 have hcard13 : (e₃ ∩ e₁).card = 1 := by rw [hC1, Finset.inter_comm X₃ e₁, hA2, Finset.inter_comm X₁ X₃]; exact hc13
The intersection e₁ ∩ e₂ is disjoint from e₃.
Any element x ∈ X₁ ∩ X₂ satisfies x ∈ X₁ ⊆ e₁ ⊆ e₁ ∪ e₂ and x ∉ X₃ (by the disjointness of X₁ ∩ X₂ and X₃), which implies X₁ ∩ X₂ ⊆ (e₁ ∪ e₂) \ X₃. Since e₃ is disjoint from (e₁ ∪ e₂) \ X₃ and e₁ ∩ e₂ = X₁ ∩ X₂, it follows that e₁ ∩ e₂ is disjoint from e₃.
uses
Finset.mem_inter.mp,Finset.disjoint_left.mp,Finset.mem_sdiff.mpr,Finset.mem_union_left,Finset.disjoint_of_subset_lefthave hsubY₃ : X₁ ∩ X₂ ⊆ (e₁ ∪ e₂) \ X₃ := by intro x hx have hx1 : x ∈ X₁ := (Finset.mem_inter.mp hx).1 have hxnotX3 : x ∉ X₃ := (Finset.disjoint_left.mp hdisjX) hx exact Finset.mem_sdiff.mpr ⟨Finset.mem_union_left _ (hX₁sube₁ hx1), hxnotX3⟩ have hdisj_e : Disjoint (e₁ ∩ e₂) e₃ := by rw [h12eq] exact Finset.disjoint_of_subset_left hsubY₃ hdisj₃.symm
The edges e₁ and e₂ are distinct (e₁ ≠ e₂).
Suppose for contradiction that e₁ = e₂. Then e₁ = e₁ ∩ e₂ = X₁ ∩ X₂. Since X₁ ⊆ e₁, this implies X₁ ⊆ X₁ ∩ X₂ ⊆ X₂, so X₁ ∩ X₂ = X₁. Substituting this into the assumption that X₁ ∩ X₂ is disjoint from X₃ means X₁ and X₃ are disjoint. But |X₃ ∩ X₁| = 1 > 0, so X₃ ∩ X₁ is nonempty, a contradiction.
uses
Finset.inter_self,Finset.mem_inter.mp,Finset.inter_eq_left.mpr,Finset.card_pos.mp,Finset.disjoint_left.mphave hne12 : e₁ ≠ e₂ := by intro heq have he1 : e₁ = X₁ ∩ X₂ := by rw [← h12eq, heq, Finset.inter_self] have hX₁subX₂ : X₁ ⊆ X₂ := by intro x hx have : x ∈ X₁ ∩ X₂ := he1 ▸ (hX₁sube₁ hx) exact (Finset.mem_inter.mp this).2 have hinter : X₁ ∩ X₂ = X₁ := Finset.inter_eq_left.mpr hX₁subX₂ rw [hinter] at hdisjX have hne : (X₃ ∩ X₁).Nonempty := Finset.card_pos.mp (by rw [hc13]; norm_num) obtain ⟨x, hx⟩ := hne have hx' := Finset.mem_inter.mp hx exact (Finset.disjoint_left.mp hdisjX) hx'.2 hx'.1
The edges e₂ and e₃ are distinct (e₂ ≠ e₃).
Suppose for contradiction that e₂ = e₃. Then e₂ = e₂ ∩ e₃ = X₂ ∩ X₃, which implies X₂ ⊆ e₂ ⊆ X₃. Then X₁ ∩ X₂ ⊆ X₂ ⊆ X₃. However, X₁ ∩ X₂ is disjoint from X₃, forcing X₁ ∩ X₂ = ∅. This contradicts the fact that |X₁ ∩ X₂| = 1.
uses
Finset.inter_self,Finset.mem_inter.mp,Finset.disjoint_left.mp,Finset.subset_empty.mphave hne23 : e₂ ≠ e₃ := by intro heq have he2 : e₂ = X₂ ∩ X₃ := by rw [← h23eq, ← heq, Finset.inter_self] have hX₂subX₃ : X₂ ⊆ X₃ := by intro x hx have : x ∈ X₂ ∩ X₃ := he2 ▸ (hX₂sube₂ hx) exact (Finset.mem_inter.mp this).2 have hsub : X₁ ∩ X₂ ⊆ X₃ := fun x hx => hX₂subX₃ (Finset.mem_inter.mp hx).2 have hemp : X₁ ∩ X₂ = ∅ := by have hz : X₁ ∩ X₂ ⊆ ∅ := by intro x hx exact absurd (hsub hx) ((Finset.disjoint_left.mp hdisjX) hx) exact Finset.subset_empty.mp hz rw [hemp] at hc12 simp at hc12
The edges e₁ and e₃ are distinct (e₁ ≠ e₃).
Suppose for contradiction that e₁ = e₃. Then e₁ = e₁ ∩ e₃ = X₁ ∩ X₃, which implies X₁ ⊆ e₁ ⊆ X₃. This in turn gives X₁ ∩ X₂ ⊆ X₁ ⊆ X₃. Since X₁ ∩ X₂ is disjoint from X₃, it follows that X₁ ∩ X₂ = ∅, contradicting |X₁ ∩ X₂| = 1.
uses
Finset.inter_self,Finset.mem_inter.mp,Finset.disjoint_left.mp,Finset.subset_empty.mphave hne13 : e₁ ≠ e₃ := by intro heq have he1 : e₁ = X₁ ∩ X₃ := by rw [← h13eq, ← heq, Finset.inter_self] have hX₁subX₃ : X₁ ⊆ X₃ := by intro x hx have : x ∈ X₁ ∩ X₃ := he1 ▸ (hX₁sube₁ hx) exact (Finset.mem_inter.mp this).2 have hsub : X₁ ∩ X₂ ⊆ X₃ := fun x hx => hX₁subX₃ (Finset.mem_inter.mp hx).1 have hemp : X₁ ∩ X₂ = ∅ := by have hz : X₁ ∩ X₂ ⊆ ∅ := by intro x hx exact absurd (hsub hx) ((Finset.disjoint_left.mp hdisjX) hx) exact Finset.subset_empty.mp hz rw [hemp] at hc12 simp at hc12
The edges e₁, e₂, e₃ form a loose triangle in H, contradicting the hypothesis that H contains no loose triangles.
Having shown that e₁, e₂, e₃ ∈ H are pairwise distinct, that their pairwise intersections each have cardinality 1, and that e₁ ∩ e₂ is disjoint from e₃, they satisfy all the defining conditions of is_loose_triangle. This directly contradicts the hypothesis h_no_lt that no three edges in H form a loose triangle, completing the proof by contradiction.
uses
is_loose_triangleexact h_no_lt e₁ he₁H e₂ he₂H e₃ he₃H (by rw [is_loose_triangle] exact ⟨hne12, hne23, hne13, hcard12, hcard23, hcard13, hdisj_e⟩)
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.disjoint_left.mp- If two sets are disjoint, then any element in the first set is not in the second set.
Finset.mem_sdiff.mpr- If an element belongs to the first set and does not belong to the second set, then it belongs to their set difference.
is_loose_triangle- Three sets form a loose triangle if they are pairwise distinct, each pair intersects in exactly one element, and the triple intersection is empty.
card_le_of_is_expandable- Any set that is expandable with parameter r has cardinality at most r.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to that of the other set.
Finset.sdiff_subset- The set difference of two sets is a subset of the first set.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.disjoint_sdiff.symm- The set difference of two sets is disjoint from the second set.
no_loose_triangle_of_expandable_sets_inter- If A ⊆ S, B ⊆ T, and S is disjoint from T \ A, then S ∩ B = A ∩ B.
Finset.subset_union_left- A set is a subset of its union with another set.
Finset.subset_union_right- A set is a subset of the union of another set with it.
Finset.inter_comm- Set intersection is commutative.
Finset.mem_inter.mp- If an element belongs to the intersection of two sets, it belongs to both sets.
Finset.mem_union_left- An element in the first set also belongs to the union of that set with another.
Finset.disjoint_of_subset_left- If a set is disjoint from another set, any subset of the first set is also disjoint from that other set.
Finset.inter_self- The intersection of any set with itself is the set itself.
Finset.inter_eq_left.mpr- If one set is a subset of another, their intersection equals the first set.
Finset.card_pos.mp- A finite set with strictly positive cardinality is nonempty.
Finset.subset_empty.mp- If a set is a subset of the empty set, it is equal to the empty set.
- Lines 1–13 prove a private helper lemma, no_loose_triangle_of_expandable_sets_inter, which is used repeatedly in the main proof to show that expanding a set preserves its intersections with other sets.
- In steps 3, 4, and 5, linear arithmetic over ℕ (the omega tactic) verifies that the sets to be avoided have cardinality at most 2 * r.
- In steps 10 and 11, simplifying the statement that an empty set has cardinality 1 (simp at hc12) closes the goal by deducing False from 0 = 1.
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.
private lemma no_loose_triangle_of_expandable_sets_inter {V : Type*} [DecidableEq V] {A B S T : Finset V} (hA : A ⊆ S) (hdisj : Disjoint S (T \ A)) (hBT : B ⊆ T) : S ∩ B = A ∩ B := by ext x simp only [Finset.mem_inter] constructor · rintro ⟨hxS, hxB⟩ by_cases hxA : x ∈ A · exact ⟨hxA, hxB⟩ · exfalso exact (Finset.disjoint_left.mp hdisj) hxS (Finset.mem_sdiff.mpr ⟨hBT hxB, hxA⟩) · rintro ⟨hxA, hxB⟩ exact ⟨hA hxA, hxB⟩/-- No three expandable sets form a loose triangle in a loose-triangle-free hypergraph. -/theorem no_loose_triangle_of_expandable_sets {V : Type*} [DecidableEq V] (H : Finset (Finset V)) (r : ℕ) (h_no_lt : ∀ e₁ ∈ H, ∀ e₂ ∈ H, ∀ e₃ ∈ H, ¬ is_loose_triangle e₁ e₂ e₃) (X₁ X₂ X₃ : Finset V) (hX₁ : IsExpandable H r X₁) (hX₂ : IsExpandable H r X₂) (hX₃ : IsExpandable H r X₃) : ¬ is_loose_triangle X₁ X₂ X₃ := by intro hlt rw [is_loose_triangle] at hlt obtain ⟨_, _, _, hc12, hc23, hc13, hdisjX⟩ := hlt have hX₂card : X₂.card ≤ r := card_le_of_is_expandable hX₂ have hX₃card : X₃.card ≤ r := card_le_of_is_expandable hX₃ obtain ⟨_, hbnd₁, hexp₁⟩ := hX₁ obtain ⟨_, hbnd₂, hexp₂⟩ := hX₂ obtain ⟨_, hbnd₃, hexp₃⟩ := hX₃ have hY₁card : ((X₂ ∪ X₃) \ X₁).card ≤ 2 * r := by have h1 := Finset.card_le_card (Finset.sdiff_subset : (X₂ ∪ X₃) \ X₁ ⊆ X₂ ∪ X₃) have h2 := Finset.card_union_le X₂ X₃ omega obtain ⟨e₁, he₁H, hX₁sube₁, hdisj₁⟩ := hexp₁ ((X₂ ∪ X₃) \ X₁) Finset.disjoint_sdiff.symm hY₁card have he₁card : e₁.card ≤ r := hbnd₁ e₁ he₁H have hY₂card : ((e₁ ∪ X₃) \ X₂).card ≤ 2 * r := by have h1 := Finset.card_le_card (Finset.sdiff_subset : (e₁ ∪ X₃) \ X₂ ⊆ e₁ ∪ X₃) have h2 := Finset.card_union_le e₁ X₃ omega obtain ⟨e₂, he₂H, hX₂sube₂, hdisj₂⟩ := hexp₂ ((e₁ ∪ X₃) \ X₂) Finset.disjoint_sdiff.symm hY₂card have he₂card : e₂.card ≤ r := hbnd₂ e₂ he₂H have hY₃card : ((e₁ ∪ e₂) \ X₃).card ≤ 2 * r := by have h1 := Finset.card_le_card (Finset.sdiff_subset : (e₁ ∪ e₂) \ X₃ ⊆ e₁ ∪ e₂) have h2 := Finset.card_union_le e₁ e₂ omega obtain ⟨e₃, he₃H, hX₃sube₃, hdisj₃⟩ := hexp₃ ((e₁ ∪ e₂) \ X₃) Finset.disjoint_sdiff.symm hY₃card have hA1 : e₁ ∩ X₂ = X₁ ∩ X₂ := no_loose_triangle_of_expandable_sets_inter hX₁sube₁ hdisj₁ Finset.subset_union_left have hA2 : e₁ ∩ X₃ = X₁ ∩ X₃ := no_loose_triangle_of_expandable_sets_inter hX₁sube₁ hdisj₁ Finset.subset_union_right have hB1 : e₂ ∩ e₁ = X₂ ∩ e₁ := no_loose_triangle_of_expandable_sets_inter hX₂sube₂ hdisj₂ Finset.subset_union_left have hB2 : e₂ ∩ X₃ = X₂ ∩ X₃ := no_loose_triangle_of_expandable_sets_inter hX₂sube₂ hdisj₂ Finset.subset_union_right have hC1 : e₃ ∩ e₁ = X₃ ∩ e₁ := no_loose_triangle_of_expandable_sets_inter hX₃sube₃ hdisj₃ Finset.subset_union_left have hC2 : e₃ ∩ e₂ = X₃ ∩ e₂ := no_loose_triangle_of_expandable_sets_inter hX₃sube₃ hdisj₃ Finset.subset_union_right have h12eq : e₁ ∩ e₂ = X₁ ∩ X₂ := by rw [Finset.inter_comm e₁ e₂, hB1, Finset.inter_comm X₂ e₁, hA1] have h23eq : e₂ ∩ e₃ = X₂ ∩ X₃ := by rw [Finset.inter_comm e₂ e₃, hC2, Finset.inter_comm X₃ e₂, hB2] have h13eq : e₁ ∩ e₃ = X₁ ∩ X₃ := by rw [Finset.inter_comm e₁ e₃, hC1, Finset.inter_comm X₃ e₁, hA2] have hcard12 : (e₁ ∩ e₂).card = 1 := by rw [h12eq]; exact hc12 have hcard23 : (e₂ ∩ e₃).card = 1 := by rw [h23eq]; exact hc23 have hcard13 : (e₃ ∩ e₁).card = 1 := by rw [hC1, Finset.inter_comm X₃ e₁, hA2, Finset.inter_comm X₁ X₃]; exact hc13 have hsubY₃ : X₁ ∩ X₂ ⊆ (e₁ ∪ e₂) \ X₃ := by intro x hx have hx1 : x ∈ X₁ := (Finset.mem_inter.mp hx).1 have hxnotX3 : x ∉ X₃ := (Finset.disjoint_left.mp hdisjX) hx exact Finset.mem_sdiff.mpr ⟨Finset.mem_union_left _ (hX₁sube₁ hx1), hxnotX3⟩ have hdisj_e : Disjoint (e₁ ∩ e₂) e₃ := by rw [h12eq] exact Finset.disjoint_of_subset_left hsubY₃ hdisj₃.symm have hne12 : e₁ ≠ e₂ := by intro heq have he1 : e₁ = X₁ ∩ X₂ := by rw [← h12eq, heq, Finset.inter_self] have hX₁subX₂ : X₁ ⊆ X₂ := by intro x hx have : x ∈ X₁ ∩ X₂ := he1 ▸ (hX₁sube₁ hx) exact (Finset.mem_inter.mp this).2 have hinter : X₁ ∩ X₂ = X₁ := Finset.inter_eq_left.mpr hX₁subX₂ rw [hinter] at hdisjX have hne : (X₃ ∩ X₁).Nonempty := Finset.card_pos.mp (by rw [hc13]; norm_num) obtain ⟨x, hx⟩ := hne have hx' := Finset.mem_inter.mp hx exact (Finset.disjoint_left.mp hdisjX) hx'.2 hx'.1 have hne23 : e₂ ≠ e₃ := by intro heq have he2 : e₂ = X₂ ∩ X₃ := by rw [← h23eq, ← heq, Finset.inter_self] have hX₂subX₃ : X₂ ⊆ X₃ := by intro x hx have : x ∈ X₂ ∩ X₃ := he2 ▸ (hX₂sube₂ hx) exact (Finset.mem_inter.mp this).2 have hsub : X₁ ∩ X₂ ⊆ X₃ := fun x hx => hX₂subX₃ (Finset.mem_inter.mp hx).2 have hemp : X₁ ∩ X₂ = ∅ := by have hz : X₁ ∩ X₂ ⊆ ∅ := by intro x hx exact absurd (hsub hx) ((Finset.disjoint_left.mp hdisjX) hx) exact Finset.subset_empty.mp hz rw [hemp] at hc12 simp at hc12 have hne13 : e₁ ≠ e₃ := by intro heq have he1 : e₁ = X₁ ∩ X₃ := by rw [← h13eq, ← heq, Finset.inter_self] have hX₁subX₃ : X₁ ⊆ X₃ := by intro x hx have : x ∈ X₁ ∩ X₃ := he1 ▸ (hX₁sube₁ hx) exact (Finset.mem_inter.mp this).2 have hsub : X₁ ∩ X₂ ⊆ X₃ := fun x hx => hX₁subX₃ (Finset.mem_inter.mp hx).1 have hemp : X₁ ∩ X₂ = ∅ := by have hz : X₁ ∩ X₂ ⊆ ∅ := by intro x hx exact absurd (hsub hx) ((Finset.disjoint_left.mp hdisjX) hx) exact Finset.subset_empty.mp hz rw [hemp] at hc12 simp at hc12 exact h_no_lt e₁ he₁H e₂ he₂H e₃ he₃H (by rw [is_loose_triangle] exact ⟨hne12, hne23, hne13, hcard12, hcard23, hcard13, hdisj_e⟩)