greedy_matching_fraction_ge_of_blocking_le
Let P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list pts of points in ℝ² in general position on which Greedy creates ℓ segments, Greedy matches at least a 2ℓ / (2ℓ + p) fraction of the input points, meaning (2ℓ)/(2ℓ+p) ≤ 2ℓ / pts.length.
Statement
theorem greedy_matching_fraction_ge_of_blocking_le (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) (hβ : segment_blocking_bound_le P ℓ p) (pts : List (ℝ × ℝ)) (h_nodup : pts.Nodup) (h_gen : points_in_general_position (pts.toFinset : Set (ℝ × ℝ))) (h_card : (greedyMatching P pts).1.card = ℓ) : (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ)
- Formalizes
- arXiv:2610.23130 Theorem 1.2 (1)
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- segment_blocking_bound_leFor a segment property P on Finset (Sym2 (ℝ × ℝ)) and natural numbers ℓ and p, segment_blocking_bound_le P ℓ p asserts that every finite…
- IsHereditarySegmentPropertyA predicate P on finite sets of unordered pairs in Sym2 (ℝ × ℝ) is a hereditary segment property if P holds on the empty finset and for…
- points_in_general_positionA set S of points in the real plane ℝ × ℝ is in general position if for all pairwise distinct points p₁, p₂, p₃ in S, the three-element…
- greedyMatchingGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P…
- segment_endpointsGiven a finite set L : Finset (Sym2 (ℝ × ℝ)) of unordered pairs of points in ℝ × ℝ, segment_endpoints L is the finset of type Finset (ℝ ×…
- greedyStepGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2…
- segments_block_points_propFor a predicate P on finite sets of unordered pairs in Sym2 (ℝ × ℝ), a finite set L of unordered pairs in Sym2 (ℝ × ℝ), and a finite set S…
- greedyMatching_nilFor every predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in ℝ × ℝ, greedyMatching P [] equals the…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- greedy_matching_ratio_equiv_blocking_boundsTheorem 1.2 (arXiv:2610.23130): Let P be a hereditary segment crossing property. (1) If the blocking number β_P(ℓ) ≤ p (every family of ℓ…
Read back from the Lean
Let $P$ be a property of finite sets of segments (unordered pairs of points in $\mathbb{R}^2$), and suppose $P$ is hereditary (it holds on the empty set, and if it holds for a set $t$, it holds for every subset $s \subseteq t$). Let $\ell, p \in \mathbb{N}$ such that $p$ is a blocking bound for $\ell$ under $P$: namely, for any finite set of segments $L$ of cardinality $\ell$ with $P(L)$ and any finite set of points $S \subset \mathbb{R}^2$, if the union of the endpoints of $L$ and the points of $S$ is in general position (no three distinct points are collinear), and $S$ is blocked by $L$ under $P$ (for every pair of distinct points $u, v \in S$, $P(L \cup \{s(u,v)\})$ is false), then $|S| \le p$. Let $pts$ be a duplicate-free list of points in $\mathbb{R}^2$ whose underlying set of points is in general position. If running the greedy matching algorithm on $pts$ with respect to $P$ produces a matching of cardinality $\ell$, then: $$\frac{2\ell}{2\ell + p} \le \frac{2\ell}{|pts|}$$ where $|pts|$ is the length of $pts$, and the division and values are in $\mathbb{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
The proof establishes that if the blocking bound β_P(ℓ) ≤ p holds for a hereditary segment property P, Greedy matches at least a 2ℓ / (2ℓ + p) fraction of the input points on any duplicate-free point set in general position yielding ℓ segments. An inductive loop invariant proves that throughout Greedy, the matched segments satisfy P, the unmatched points are blocked by the segments, and their union forms the input points. The blocking bound bounds the unmatched points by p, and the ℓ segments contribute at most 2ℓ endpoints, bounding the total input size by 2ℓ + p. Dividing 2ℓ by this upper bound yields the desired fraction lower bound.
The endpoints of insert s(u, v) M are {u, v} ∪ segment_endpoints M.
Unfolding the definition of segment endpoints as a big union over segments and distributing the union over the inserted segment.
uses
Finset.biUnion_insertlemma greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair (u v : ℝ × ℝ) (M : Finset (Sym2 (ℝ × ℝ))) : segment_endpoints (insert s(u, v) M) = {u, v} ∪ segment_endpoints M := by simp [segment_endpoints, Finset.biUnion_insert]
The empty set of segments has at most 2 * 0 endpoints.
Base case of induction on the set of segments L: the empty set has no endpoints, and 0 ≤ 0 holds by simplification.
uses
Finset.induction_onlemma greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le (L : Finset (Sym2 (ℝ × ℝ))) : (segment_endpoints L).card ≤ 2 * L.card := by classical induction L using Finset.induction_on with | empty => simp [segment_endpoints]
Any finite set of segments L has at most 2 * |L| endpoints.
By induction, each inserted segment s(u, v) adds at most its two endpoints {u, v}; by subadditivity of cardinality, the number of endpoints grows by at most 2.
uses
Sym2.ind,greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair,Finset.card_union_le,Nat.add_le_add,Finset.card_le_two,Finset.card_insert_of_notMem| insert a L ha ih => induction a using Sym2.ind with | _ u v => rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair] calc (({u, v} : Finset (ℝ × ℝ)) ∪ segment_endpoints L).card ≤ ({u, v} : Finset (ℝ × ℝ)).card + (segment_endpoints L).card := Finset.card_union_le _ _ _ ≤ 2 + 2 * L.card := Nat.add_le_add Finset.card_le_two ih _ = 2 * (insert s(u, v) L).card := by rw [Finset.card_insert_of_notMem ha]; ringIn the empty list, erasing a does not contain a.
Base case of induction on list l: [].erase a is empty, which contains no elements.
lemma greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) : a ∉ l.erase a := by induction l with | nil => simp
In any duplicate-free list l, erasing a yields a list not containing a.
For a non-empty duplicate-free list b :: t, if b = a, erasing a leaves t (which does not contain a because the list has no duplicates); if b ≠ a, erasing a recurses on t, so a is neither b nor in t.erase a by induction.
uses
List.nodup_cons,List.erase_cons_head,List.erase_cons,if_neg| cons b t ih => rw [List.nodup_cons] at h obtain ⟨hbt, ht⟩ := h by_cases hba : b = a · subst hba rw [List.erase_cons_head] exact hbt · rw [List.erase_cons] simp only [beq_iff_eq] rw [if_neg hba] simp only [List.mem_cons, not_or] exact ⟨fun hab => hba hab.symm, ih ht⟩For a duplicate-free list l, an element x is in (l.erase a).toFinset if and only if x ∈ l.toFinset and x ≠ a.
Any element of l.erase a belongs to l and cannot be a by the previous lemma; conversely, any element of l other than a is preserved by erase.
uses
List.mem_toFinset,List.mem_of_mem_erase,greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self,List.mem_erase_of_nelemma greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset (l : List (ℝ × ℝ)) (h : l.Nodup) (a x : ℝ × ℝ) : x ∈ (l.erase a).toFinset ↔ x ∈ l.toFinset ∧ x ≠ a := by simp only [List.mem_toFinset] constructor · intro hx refine ⟨List.mem_of_mem_erase (a := x) (b := a) (l := l) hx, ?_⟩ rintro rfl exact greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self l h x hx · rintro ⟨hx, hne⟩ exact (List.mem_erase_of_ne (a := x) (b := a) (l := l) hne).mpr hx
For a duplicate-free list l with a ∈ l, insert a (l.erase a).toFinset = l.toFinset.
By extensionality: inserting a back into the elements of l.erase a covers a (which is in l) and all other elements of l, recovering l.toFinset.
uses
greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset,Or.inl,Or.inrlemma greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) (ha : a ∈ l) : insert a (l.erase a).toFinset = l.toFinset := by ext x simp only [Finset.mem_insert, List.mem_toFinset, greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset l h a x] constructor · rintro (rfl | ⟨hx, _⟩) · exact ha · exact hx · intro hx by_cases hxa : x = a · exact Or.inl hxa · exact Or.inr ⟨hx, hxa⟩
If E ∪ insert u Ke = W, then {u, a} ∪ E ∪ Ke = W ∪ {a}. automation
Substituting W with E ∪ {u} ∪ Ke, both sides describe the set E ∪ Ke ∪ {u, a}; the goal is closed by propositional logic.
lemma greedy_matching_fraction_ge_of_blocking_le_some_union (E Ke W : Finset (ℝ × ℝ)) (u a : ℝ × ℝ) (hE : E ∪ insert u Ke = W) : ({u, a} : Finset (ℝ × ℝ)) ∪ E ∪ Ke = W ∪ {a} := by rw [← hE] ext x simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton] tauto
Unpack the inductive invariant for the state (M, U) and expand greedyStep into a search for an eligible match for point a.
Extract the four components of the invariant (P M, U blocked by M, U duplicate-free, endpoints ∪ U = w) and case-split on whether List.find? finds a point u ∈ U that can match with a while preserving P.
lemma greedy_matching_fraction_ge_of_blocking_le_step (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (w : List (ℝ × ℝ)) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) (a : ℝ × ℝ) (hinv : greedy_matching_fraction_ge_of_blocking_le_inv P w M U) (ha : a ∉ w.toFinset) : greedy_matching_fraction_ge_of_blocking_le_inv P (w ++ [a]) (greedyStep P (M, U) a).1 (greedyStep P (M, U) a).2 := by obtain ⟨hPM, hblk, hUnd, heq⟩ := hinv classical let g : ℝ × ℝ → Bool := fun u => decide (P (insert s(u, a) M)) have hgd : greedyStep P (M, U) a = (match List.find? g U with | some u => (insert s(u, a) M, U.erase u) | none => (M, U ++ [a])) := rfl rw [hgd] cases hf : List.find? g U with
When an eligible point u ∈ U is matched with a, P holds for the new matching, remaining points are blocked, and U.erase u has no duplicates.
By construction, P holds on insert s(u, a) M. Any two points in U.erase u cannot form a valid segment with M by the inductive hypothesis, hence not with insert s(u, a) M because P is hereditary. Erasing u from a duplicate-free list preserves the duplicate-free property.
uses
of_decide_eq_true,List.find?_some,greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset,Finset.insert_subset_insert,Finset.subset_insert,List.Nodup.erase| some u => refine ⟨?_, ?_, ?_, ?_⟩ · exact of_decide_eq_true (by simpa [g] using List.find?_some hf) · intro x y hx hy hxy hbig obtain ⟨hxU, hxu⟩ := (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u x).mp hx obtain ⟨hyU, hyu⟩ := (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u y).mp hy exact hblk hxU hyU hxy (hP.2 (Finset.insert_subset_insert s(x, y) (Finset.subset_insert s(u, a) M)) hbig) · exact List.Nodup.erase u hUndWhen u is matched with a, the union of segment endpoints and remaining unmatched points equals (w ++ [a]).toFinset.
The new endpoints are {u, a} ∪ segment_endpoints M, and the remaining unmatched points are (U.erase u).toFinset. Since insert u (U.erase u).toFinset = U.toFinset, the union rearrangement lemma gives w.toFinset ∪ {a}, which equals (w ++ [a]).toFinset.
uses
greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair,List.mem_of_find?_eq_some,greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset,greedy_matching_fraction_ge_of_blocking_le_some_union,List.toFinset_append· rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair] have hu : u ∈ U := List.mem_of_find?_eq_some hf have hUins : insert u (U.erase u).toFinset = U.toFinset := greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset U hUnd u hu have hE : segment_endpoints M ∪ insert u (U.erase u).toFinset = w.toFinset := by rw [hUins]; exact heq rw [greedy_matching_fraction_ge_of_blocking_le_some_union (segment_endpoints M) (U.erase u).toFinset w.toFinset u a hE] rw [List.toFinset_append] simp | none =>
When no point in U can match with a, P M still holds and U ∪ {a} is blocked by M.
The matching M is unchanged, so P M holds. For any distinct x, y ∈ U ∪ {a}, if both are in U they are blocked by the induction hypothesis; if one is a and the other z ∈ U, the fact that find? returned none implies insert s(z, a) M does not satisfy P.
uses
of_decide_eq_false,Sym2.eq_swaprefine ⟨?_, ?_, ?_, ?_⟩ · exact hPM · intro x y hx hy hxy have hxn : x ∈ U.toFinset ∨ x = a := by rcases (by simpa using hx : x = a ∨ x ∈ U.toFinset) with h | h · exact Or.inr h · exact Or.inl h have hyn : y ∈ U.toFinset ∨ y = a := by rcases (by simpa using hy : y = a ∨ y ∈ U.toFinset) with h | h · exact Or.inr h · exact Or.inl h have hg : ∀ z ∈ U.toFinset, ¬ P (insert s(z, a) M) := by intro z hz have hzf : g z = false := by have h1 : ¬ g z = true := (List.find?_eq_none.mp hf) z (List.mem_toFinset.mp hz) exact Bool.eq_false_iff.mpr h1 exact of_decide_eq_false (by simpa [g] using hzf) rcases hxn with hxU | rfl · rcases hyn with hyU | rfl · exact hblk hxU hyU hxy · exact hg x hxU · rcases hyn with hyU | rfl · have h1 := hg y hyU rwa [Sym2.eq_swap] at h1 · exact absurd rfl hxy
When a remains unmatched, U ++ [a] has no duplicates and the union of endpoints and unmatched points equals (w ++ [a]).toFinset.
Since a ∉ w and U ⊆ w, a ∉ U, so appending a preserves the duplicate-free property. The union of endpoints and U ++ [a] associates to (segment_endpoints M ∪ U) ∪ {a} = w ∪ {a}.
uses
Finset.subset_union_right,List.mem_toFinset,List.nodup_append,List.nodup_singleton,List.mem_singleton,List.toFinset_append,Finset.union_assoc· have hUsub : U.toFinset ⊆ w.toFinset := by rw [← heq]; exact Finset.subset_union_right have haUf : a ∉ U.toFinset := fun h => ha (hUsub h) have haU : a ∉ U := fun h => haUf (List.mem_toFinset.mpr h) rw [List.nodup_append] refine ⟨hUnd, List.nodup_singleton a, ?_⟩ intro x hx y hy rw [List.mem_singleton] at hy subst hy exact fun hxa => haU (hxa ▸ hx) · rw [List.toFinset_append, ← Finset.union_assoc, heq] simp [List.toFinset_append]
The loop invariant holds at the base case pts = [].
Greedy matching on the empty list returns (∅, []), for which P holds by the hereditary property, blocking is vacuously true on the empty set, [] has no duplicates, and the endpoints union is empty.
uses
greedyMatching_nillemma greedy_matching_fraction_ge_of_blocking_le_inv_nodup (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (pts : List (ℝ × ℝ)) (h : pts.Nodup) : greedy_matching_fraction_ge_of_blocking_le_inv P pts (greedyMatching P pts).1 (greedyMatching P pts).2 := by classical induction pts using List.reverseRecOn with | nil => rw [greedyMatching_nil] refine ⟨hP.1, ?_, ?_, ?_⟩ · intro u v hu hv huv simp at hu · simp · simp [segment_endpoints]
The loop invariant holds after running Greedy on any duplicate-free list of points.
By reverse induction on pts, adding the next point a using greedyStep preserves the invariant by greedy_matching_fraction_ge_of_blocking_le_step, since a ∉ w follows from pts having no duplicates.
uses
List.nodup_append,List.mem_toFinset,List.foldl_append,greedy_matching_fraction_ge_of_blocking_le_step,Prod.mk.eta| append_singleton w a ih => obtain ⟨hw, _, hdisj⟩ := List.nodup_append.mp h have ha : a ∉ w.toFinset := by intro haw exact (hdisj a (List.mem_toFinset.mp haw) a (by simp)) rfl have hgm : greedyMatching P (w ++ [a]) = greedyStep P (greedyMatching P w) a := by simp [greedyMatching, List.foldl_append] rw [hgm] have hstep := greedy_matching_fraction_ge_of_blocking_le_step P hP w (greedyMatching P w).1 (greedyMatching P w).2 a (ih hw) ha rw [Prod.mk.eta] at hstep exact hstepThe state after running Greedy on pts satisfies the loop invariant.
Instantiate greedy_matching_fraction_ge_of_blocking_le_inv_nodup with the duplicate-free list pts.
uses
greedy_matching_fraction_ge_of_blocking_le_inv_nodup/-- Part (1) of Theorem 1.2: if β_P(ℓ) ≤ p, Greedy matches at least a 2ℓ/(2ℓ+p) fraction on every input producing ℓ segments. -/ theorem greedy_matching_fraction_ge_of_blocking_le (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) (hβ : segment_blocking_bound_le P ℓ p) (pts : List (ℝ × ℝ)) (h_nodup : pts.Nodup) (h_gen : points_in_general_position (pts.toFinset : Set (ℝ × ℝ))) (h_card : (greedyMatching P pts).1.card = ℓ) : (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ) := by classical obtain ⟨hPM, hblk, hUnd, heq⟩ := greedy_matching_fraction_ge_of_blocking_le_inv_nodup P hP pts h_nodup
The union of the segment endpoints and the unmatched points is in general position.
Because the union of the segment endpoints and the unmatched points equals the set of input points pts, it inherits general position from the hypothesis on pts.
uses
Finset.coe_unionhave hgen' : points_in_general_position ((↑(segment_endpoints (greedyMatching P pts).1) : Set (ℝ × ℝ)) ∪ (↑(greedyMatching P pts).2.toFinset : Set (ℝ × ℝ))) := by rw [← Finset.coe_union, heq] exact h_gen
There are at most p unmatched points.
By definition of the blocking bound β_P(ℓ) ≤ p, any set of points in general position blocked by ℓ segments satisfying P has cardinality at most p.
have hUcard : (greedyMatching P pts).2.toFinset.card ≤ p := hβ (greedyMatching P pts).1 (greedyMatching P pts).2.toFinset h_card hPM hgen' hblkThe ℓ matched segments have at most 2ℓ endpoints.
Applying greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le to the matching of size ℓ shows that its endpoints number at most 2ℓ.
uses
greedy_matching_fraction_ge_of_blocking_le_endpoints_card_lehave hends : (segment_endpoints (greedyMatching P pts).1).card ≤ 2 * ℓ := by have h := greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le (greedyMatching P pts).1 rwa [h_card] at h
The total number of input points is at most 2ℓ + p.
The set of input points is the union of the segment endpoints (at most 2ℓ) and the unmatched points (at most p); by subadditivity of cardinality, |pts| ≤ 2ℓ + p.
uses
List.toFinset_card_of_nodup,Finset.card_union_le,Nat.add_le_addhave hlen : pts.length ≤ 2 * ℓ + p := by rw [← List.toFinset_card_of_nodup h_nodup] calc pts.toFinset.card = (segment_endpoints (greedyMatching P pts).1 ∪ (greedyMatching P pts).2.toFinset).card := by rw [heq] _ ≤ (segment_endpoints (greedyMatching P pts).1).card + (greedyMatching P pts).2.toFinset.card := Finset.card_union_le _ _ _ ≤ 2 * ℓ + p := Nat.add_le_add hends hUcard
The desired inequality holds when ℓ = 0.
When ℓ = 0, the numerator 2ℓ is 0, so both sides evaluate to 0 and the inequality holds trivially.
uses
Nat.eq_zero_or_posrcases Nat.eq_zero_or_pos ℓ with hℓ0 | hℓpos · subst hℓ0 simp
When ℓ > 0, the input list pts is non-empty.
If pts were empty, Greedy would produce 0 segments, contradicting ℓ > 0. Thus |pts| > 0.
uses
Nat.eq_zero_or_pos,List.length_eq_zero_iff,greedyMatching_nil· have hnpos : 0 < pts.length := by rcases Nat.eq_zero_or_pos pts.length with h0 | hpos · exfalso have hnil : pts = [] := List.length_eq_zero_iff.mp h0 subst hnil rw [greedyMatching_nil] at h_card simp at h_card omega · exact hpos
The inequality (2ℓ) / (2ℓ + p) ≤ 2ℓ / |pts| holds.
Since 0 < |pts| ≤ 2ℓ + p and 2ℓ ≥ 0, dividing 2ℓ by the larger quantity 2ℓ + p yields a smaller or equal quotient than dividing by |pts|.
uses
div_le_div_of_nonneg_lefthave hden : (0 : ℝ) < (pts.length : ℝ) := by exact_mod_cast hnpos have hle : (pts.length : ℝ) ≤ 2 * (ℓ : ℝ) + (p : ℝ) := by exact_mod_cast hlen exact div_le_div_of_nonneg_left (by positivity) hden hle
Finset.biUnion_insert- The big union of a function over insert a s is the value at a united with the big union over s.
Finset.induction_on- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved by inserting an element not already in the set.
Sym2.ind- Every element of the symmetric square Sym2 α is an unordered pair s(u, v).
greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair- Adding a segment s(u, v) to a set of segments M adds {u, v} to its set of endpoints.
Finset.card_union_le- The cardinality of a union of finite sets is at most the sum of their cardinalities.
Nat.add_le_add- Adding inequalities preserves ordering on natural numbers.
Finset.card_le_two- A pair set {a, b} has cardinality at most 2.
Finset.card_insert_of_notMem- Inserting an element not in a finite set increases its cardinality by 1.
List.nodup_cons- A list b :: t has no duplicates if and only if b ∉ t and t has no duplicates.
List.erase_cons_head- Erasing the head element a from a :: l leaves l.
List.erase_cons- Erasing from b :: l inspects whether b = a, returning l if equal, and b :: l.erase a otherwise.
if_neg- An if-then-else on a false condition simplifies to the else branch.
List.mem_toFinset- An element belongs to l.toFinset if and only if it belongs to l.
List.mem_of_mem_erase- Any element of l.erase b belongs to l.
greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self- For a duplicate-free list l, an element a does not belong to l.erase a.
List.mem_erase_of_ne- For a ≠ b, an element belongs to l.erase b if and only if it belongs to l.
greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset- For a duplicate-free list l, x ∈ (l.erase a).toFinset if and only if x ∈ l and x ≠ a.
Or.inl- Constructs a proof of a ∨ b from a proof of a.
Or.inr- Constructs a proof of a ∨ b from a proof of b.
of_decide_eq_true- If decide p evaluates to true, then p is true.
List.find?_some- If List.find? finds an element, that element satisfies the predicate.
Finset.insert_subset_insert- If s ⊆ t, then insert a s ⊆ insert a t.
Finset.subset_insert- A set s is a subset of insert a s.
List.Nodup.erase- Erasing an element from a duplicate-free list preserves the duplicate-free property.
List.mem_of_find?_eq_some- If List.find? finds an element in l, that element belongs to l.
greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset- For a duplicate-free list l and a ∈ l, inserting a into (l.erase a).toFinset recovers l.toFinset.
greedy_matching_fraction_ge_of_blocking_le_some_union- If E ∪ insert u Ke = W, then {u, a} ∪ E ∪ Ke = W ∪ {a}.
List.toFinset_append- The set of elements of an appended list is the union of their sets of elements.
of_decide_eq_false- If decide p evaluates to false, then ¬p is true.
Sym2.eq_swap- The unordered pair s(a, b) equals s(b, a).
Finset.subset_union_right- A set s₂ is a subset of s₁ ∪ s₂.
List.nodup_append- The concatenation of two lists has no duplicates if and only if each has no duplicates and they are disjoint.
List.nodup_singleton- A singleton list [a] has no duplicates.
List.mem_singleton- An element belongs to [b] if and only if it equals b.
Finset.union_assoc- Union of finite sets is associative.
greedyMatching_nil- Greedy matching on the empty list produces no segments and no unmatched points.
List.foldl_append- Folding over an appended list equals folding over the first list, then over the second.
greedy_matching_fraction_ge_of_blocking_le_step- The greedy matching invariant is preserved when a new point is processed by greedyStep.
Prod.mk.eta- Every pair p satisfies (p.1, p.2) = p.
greedy_matching_fraction_ge_of_blocking_le_inv_nodup- The greedy matching invariant holds after running on any duplicate-free list of points.
Finset.coe_union- The set coercion of a union of finite sets is the union of their set coercions.
greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le- A set of segments L has at most 2 * |L| endpoints.
List.toFinset_card_of_nodup- The cardinality of the set of elements of a duplicate-free list equals its length.
Nat.eq_zero_or_pos- Every natural number is either 0 or strictly positive.
List.length_eq_zero_iff- A list has length 0 if and only if it is empty.
div_le_div_of_nonneg_left- If c ≥ 0 and 0 < a ≤ b, then c / b ≤ c / a.
- The greedy algorithm is formalized as a fold over the input list of points, tracking a pair (M, U) where M is the set of formed segments and U is the list of unmatched points.
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.
def greedy_matching_fraction_ge_of_blocking_le_inv (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (w : List (ℝ × ℝ)) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) : Prop := P M ∧ segments_block_points_prop P M U.toFinset ∧ U.Nodup ∧ segment_endpoints M ∪ U.toFinset = w.toFinsetlemma greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair (u v : ℝ × ℝ) (M : Finset (Sym2 (ℝ × ℝ))) : segment_endpoints (insert s(u, v) M) = {u, v} ∪ segment_endpoints M := by simp [segment_endpoints, Finset.biUnion_insert]lemma greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le (L : Finset (Sym2 (ℝ × ℝ))) : (segment_endpoints L).card ≤ 2 * L.card := by classical induction L using Finset.induction_on with | empty => simp [segment_endpoints] | insert a L ha ih => induction a using Sym2.ind with | _ u v => rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair] calc (({u, v} : Finset (ℝ × ℝ)) ∪ segment_endpoints L).card ≤ ({u, v} : Finset (ℝ × ℝ)).card + (segment_endpoints L).card := Finset.card_union_le _ _ _ ≤ 2 + 2 * L.card := Nat.add_le_add Finset.card_le_two ih _ = 2 * (insert s(u, v) L).card := by rw [Finset.card_insert_of_notMem ha]; ringlemma greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) : a ∉ l.erase a := by induction l with | nil => simp | cons b t ih => rw [List.nodup_cons] at h obtain ⟨hbt, ht⟩ := h by_cases hba : b = a · subst hba rw [List.erase_cons_head] exact hbt · rw [List.erase_cons] simp only [beq_iff_eq] rw [if_neg hba] simp only [List.mem_cons, not_or] exact ⟨fun hab => hba hab.symm, ih ht⟩lemma greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset (l : List (ℝ × ℝ)) (h : l.Nodup) (a x : ℝ × ℝ) : x ∈ (l.erase a).toFinset ↔ x ∈ l.toFinset ∧ x ≠ a := by simp only [List.mem_toFinset] constructor · intro hx refine ⟨List.mem_of_mem_erase (a := x) (b := a) (l := l) hx, ?_⟩ rintro rfl exact greedy_matching_fraction_ge_of_blocking_le_not_mem_erase_self l h x hx · rintro ⟨hx, hne⟩ exact (List.mem_erase_of_ne (a := x) (b := a) (l := l) hne).mpr hxlemma greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset (l : List (ℝ × ℝ)) (h : l.Nodup) (a : ℝ × ℝ) (ha : a ∈ l) : insert a (l.erase a).toFinset = l.toFinset := by ext x simp only [Finset.mem_insert, List.mem_toFinset, greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset l h a x] constructor · rintro (rfl | ⟨hx, _⟩) · exact ha · exact hx · intro hx by_cases hxa : x = a · exact Or.inl hxa · exact Or.inr ⟨hx, hxa⟩lemma greedy_matching_fraction_ge_of_blocking_le_some_union (E Ke W : Finset (ℝ × ℝ)) (u a : ℝ × ℝ) (hE : E ∪ insert u Ke = W) : ({u, a} : Finset (ℝ × ℝ)) ∪ E ∪ Ke = W ∪ {a} := by rw [← hE] ext x simp only [Finset.mem_union, Finset.mem_insert, Finset.mem_singleton] tautolemma greedy_matching_fraction_ge_of_blocking_le_step (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (w : List (ℝ × ℝ)) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) (a : ℝ × ℝ) (hinv : greedy_matching_fraction_ge_of_blocking_le_inv P w M U) (ha : a ∉ w.toFinset) : greedy_matching_fraction_ge_of_blocking_le_inv P (w ++ [a]) (greedyStep P (M, U) a).1 (greedyStep P (M, U) a).2 := by obtain ⟨hPM, hblk, hUnd, heq⟩ := hinv classical let g : ℝ × ℝ → Bool := fun u => decide (P (insert s(u, a) M)) have hgd : greedyStep P (M, U) a = (match List.find? g U with | some u => (insert s(u, a) M, U.erase u) | none => (M, U ++ [a])) := rfl rw [hgd] cases hf : List.find? g U with | some u => refine ⟨?_, ?_, ?_, ?_⟩ · exact of_decide_eq_true (by simpa [g] using List.find?_some hf) · intro x y hx hy hxy hbig obtain ⟨hxU, hxu⟩ := (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u x).mp hx obtain ⟨hyU, hyu⟩ := (greedy_matching_fraction_ge_of_blocking_le_mem_erase_toFinset U hUnd u y).mp hy exact hblk hxU hyU hxy (hP.2 (Finset.insert_subset_insert s(x, y) (Finset.subset_insert s(u, a) M)) hbig) · exact List.Nodup.erase u hUnd · rw [greedy_matching_fraction_ge_of_blocking_le_endpoints_insert_pair] have hu : u ∈ U := List.mem_of_find?_eq_some hf have hUins : insert u (U.erase u).toFinset = U.toFinset := greedy_matching_fraction_ge_of_blocking_le_insert_erase_toFinset U hUnd u hu have hE : segment_endpoints M ∪ insert u (U.erase u).toFinset = w.toFinset := by rw [hUins]; exact heq rw [greedy_matching_fraction_ge_of_blocking_le_some_union (segment_endpoints M) (U.erase u).toFinset w.toFinset u a hE] rw [List.toFinset_append] simp | none => refine ⟨?_, ?_, ?_, ?_⟩ · exact hPM · intro x y hx hy hxy have hxn : x ∈ U.toFinset ∨ x = a := by rcases (by simpa using hx : x = a ∨ x ∈ U.toFinset) with h | h · exact Or.inr h · exact Or.inl h have hyn : y ∈ U.toFinset ∨ y = a := by rcases (by simpa using hy : y = a ∨ y ∈ U.toFinset) with h | h · exact Or.inr h · exact Or.inl h have hg : ∀ z ∈ U.toFinset, ¬ P (insert s(z, a) M) := by intro z hz have hzf : g z = false := by have h1 : ¬ g z = true := (List.find?_eq_none.mp hf) z (List.mem_toFinset.mp hz) exact Bool.eq_false_iff.mpr h1 exact of_decide_eq_false (by simpa [g] using hzf) rcases hxn with hxU | rfl · rcases hyn with hyU | rfl · exact hblk hxU hyU hxy · exact hg x hxU · rcases hyn with hyU | rfl · have h1 := hg y hyU rwa [Sym2.eq_swap] at h1 · exact absurd rfl hxy · have hUsub : U.toFinset ⊆ w.toFinset := by rw [← heq]; exact Finset.subset_union_right have haUf : a ∉ U.toFinset := fun h => ha (hUsub h) have haU : a ∉ U := fun h => haUf (List.mem_toFinset.mpr h) rw [List.nodup_append] refine ⟨hUnd, List.nodup_singleton a, ?_⟩ intro x hx y hy rw [List.mem_singleton] at hy subst hy exact fun hxa => haU (hxa ▸ hx) · rw [List.toFinset_append, ← Finset.union_assoc, heq] simp [List.toFinset_append]lemma greedy_matching_fraction_ge_of_blocking_le_inv_nodup (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (pts : List (ℝ × ℝ)) (h : pts.Nodup) : greedy_matching_fraction_ge_of_blocking_le_inv P pts (greedyMatching P pts).1 (greedyMatching P pts).2 := by classical induction pts using List.reverseRecOn with | nil => rw [greedyMatching_nil] refine ⟨hP.1, ?_, ?_, ?_⟩ · intro u v hu hv huv simp at hu · simp · simp [segment_endpoints] | append_singleton w a ih => obtain ⟨hw, _, hdisj⟩ := List.nodup_append.mp h have ha : a ∉ w.toFinset := by intro haw exact (hdisj a (List.mem_toFinset.mp haw) a (by simp)) rfl have hgm : greedyMatching P (w ++ [a]) = greedyStep P (greedyMatching P w) a := by simp [greedyMatching, List.foldl_append] rw [hgm] have hstep := greedy_matching_fraction_ge_of_blocking_le_step P hP w (greedyMatching P w).1 (greedyMatching P w).2 a (ih hw) ha rw [Prod.mk.eta] at hstep exact hstep/-- Part (1) of Theorem 1.2: if β_P(ℓ) ≤ p, Greedy matches at least a 2ℓ/(2ℓ+p) fraction on every input producing ℓ segments. -/theorem greedy_matching_fraction_ge_of_blocking_le (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) (hβ : segment_blocking_bound_le P ℓ p) (pts : List (ℝ × ℝ)) (h_nodup : pts.Nodup) (h_gen : points_in_general_position (pts.toFinset : Set (ℝ × ℝ))) (h_card : (greedyMatching P pts).1.card = ℓ) : (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ) := by classical obtain ⟨hPM, hblk, hUnd, heq⟩ := greedy_matching_fraction_ge_of_blocking_le_inv_nodup P hP pts h_nodup have hgen' : points_in_general_position ((↑(segment_endpoints (greedyMatching P pts).1) : Set (ℝ × ℝ)) ∪ (↑(greedyMatching P pts).2.toFinset : Set (ℝ × ℝ))) := by rw [← Finset.coe_union, heq] exact h_gen have hUcard : (greedyMatching P pts).2.toFinset.card ≤ p := hβ (greedyMatching P pts).1 (greedyMatching P pts).2.toFinset h_card hPM hgen' hblk have hends : (segment_endpoints (greedyMatching P pts).1).card ≤ 2 * ℓ := by have h := greedy_matching_fraction_ge_of_blocking_le_endpoints_card_le (greedyMatching P pts).1 rwa [h_card] at h have hlen : pts.length ≤ 2 * ℓ + p := by rw [← List.toFinset_card_of_nodup h_nodup] calc pts.toFinset.card = (segment_endpoints (greedyMatching P pts).1 ∪ (greedyMatching P pts).2.toFinset).card := by rw [heq] _ ≤ (segment_endpoints (greedyMatching P pts).1).card + (greedyMatching P pts).2.toFinset.card := Finset.card_union_le _ _ _ ≤ 2 * ℓ + p := Nat.add_le_add hends hUcard rcases Nat.eq_zero_or_pos ℓ with hℓ0 | hℓpos · subst hℓ0 simp · have hnpos : 0 < pts.length := by rcases Nat.eq_zero_or_pos pts.length with h0 | hpos · exfalso have hnil : pts = [] := List.length_eq_zero_iff.mp h0 subst hnil rw [greedyMatching_nil] at h_card simp at h_card omega · exact hpos have hden : (0 : ℝ) < (pts.length : ℝ) := by exact_mod_cast hnpos have hle : (pts.length : ℝ) ≤ 2 * (ℓ : ℝ) + (p : ℝ) := by exact_mod_cast hlen exact div_le_div_of_nonneg_left (by positivity) hden hle