AFTD Auto-Formalizing Theoretical Domains

greedy_matching_ratio_equiv_blocking_bounds

theoremverifiedformalization

Theorem 1.2 (arXiv:2610.23130): Let P be a hereditary segment crossing property. (1) If the blocking number β_P(ℓ) ≤ p (every family of ℓ segments satisfying P blocks at most p points in general position), then on every input of points in general position on which Greedy creates ℓ segments, Greedy matches at least a 2ℓ / (2ℓ + p) fraction of the input points. (2) If β_P(ℓ) ≥ p (there exists a family of ℓ disjoint segments satisfying P blocking at least p points in general position), then there exists an input on which Greedy creates ℓ segments and matches at most a 2ℓ / (2ℓ + p) fraction of the input points.

Statement

theorem greedy_matching_ratio_equiv_blocking_bounds
    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) :
    (segment_blocking_bound_le P ℓ p →
      ∀ pts : List (ℝ × ℝ), pts.Nodup → points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) →
        (greedyMatching P pts).1.card = ℓ →
        (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ)) ∧
    (segment_blocking_bound_ge P ℓ p →
      ∃ pts : List (ℝ × ℝ), pts.Nodup ∧ points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) ∧
        (greedyMatching P pts).1.card = ℓ ∧
        (2 * (ℓ : ℝ)) / (pts.length : ℝ) ≤ (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)))
Formalizes
arXiv:2610.23130 Theorem 1.2
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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…
  • segment_blocking_bound_geFor a segment property P on Finset (Sym2 (ℝ × ℝ)) and natural numbers ℓ and p, segment_blocking_bound_ge P ℓ p asserts that there exists a…
  • 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…
  • greedy_matching_fraction_ge_of_blocking_leLet P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list…
  • greedy_matching_fraction_le_of_blocking_geLet P be a hereditary segment property. If β_P(ℓ) ≥ p (formalized by segment_blocking_bound_ge P ℓ p), then there exists a duplicate-free…

Read back from the Lean

The theorem asserts that for any property P on finite sets of segments (unordered pairs of points in ℝ²), any hypothesis hP that P is hereditary (holds on ∅ and closed under subsets), and any natural numbers ℓ and p: Both of the following hold: 1. **(Upper bound implies matching ratio lower bound):** If segment_blocking_bound_le P ℓ p holds—meaning that whenever L is a segment set of size ℓ satisfying P, and S is a point set such that the endpoints of L together with S are in general position and no pair of distinct points in S can form a segment added to L while preserving P, then |S| ≤ p— then for every duplicate-free list of points pts in ℝ² whose underlying set is in general position, if the greedy matching algorithm using P on pts produces a matching of cardinality ℓ, then (2 * ℓ) / (2 * ℓ + p) ≤ (2 * ℓ) / pts.length. 2. **(Lower bound implies matching ratio upper bound):** If segment_blocking_bound_ge P ℓ p holds—meaning that there exist a segment set L of size ℓ satisfying P with 2 * ℓ distinct endpoints and a point set S disjoint from L's endpoints, such that their union is in general position, S is blocked by L under P, and |S| ≥ p— then there exists a duplicate-free list of points pts in ℝ² in general position such that the greedy matching on pts produces a matching of cardinality ℓ, and (2 * ℓ) / pts.length ≤ (2 * ℓ) / (2 * ℓ + p).

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

Theorem 1.2 establishes the equivalence between blocking numbers and the competitive ratio of the Greedy matching algorithm. The proof splits into two independent implications, each resolved by applying an already proven theorem: the lower bound on the fraction matched follows from `greedy_matching_fraction_ge_of_blocking_le`, and the existence of a matching ratio upper bound witness follows from `greedy_matching_fraction_le_of_blocking_ge`.

  1. The theorem decomposes into two separate implications: the lower bound on the matching fraction and the upper bound / worst-case existence.

    The goal is a conjunction of two statements, so we split it into two subgoals using `constructor`.

    line 12

      constructor
  2. If every family of ℓ segments blocks at most p points, Greedy matches at least a 2ℓ / (2ℓ + p) fraction of the points on any input where it forms ℓ segments.

    We assume the blocking upper bound hypothesis, an arbitrary duplicate-free list of points in general position, and the assumption that Greedy selects ℓ segments. This direction is established immediately by applying `greedy_matching_fraction_ge_of_blocking_le`.

    lines 13–14

    uses greedy_matching_fraction_ge_of_blocking_le

      · intro hβ pts h_nodup h_gen h_card
        exact greedy_matching_fraction_ge_of_blocking_le P hP ℓ p hβ pts h_nodup h_gen h_card
  3. If there exists a family of ℓ segments blocking at least p points, then there exists an input where Greedy forms ℓ segments and matches at most a 2ℓ / (2ℓ + p) fraction of points.

    We assume the existence of ℓ disjoint segments blocking at least p points. Applying `greedy_matching_fraction_le_of_blocking_ge` directly yields the desired adversarial point set in general position.

    lines 15–16

    uses greedy_matching_fraction_le_of_blocking_ge

      · intro hβ
        exact greedy_matching_fraction_le_of_blocking_ge P hP ℓ p hβ
greedy_matching_fraction_ge_of_blocking_le
For a hereditary segment property P, if any ℓ segments satisfying P block at most p points in general position, then on every duplicate-free input sequence of points in general position on which Greedy produces ℓ segments, the fraction of points matched is at least 2ℓ / (2ℓ + p).
greedy_matching_fraction_le_of_blocking_ge
For a hereditary segment property P, if there exists a set of ℓ disjoint segments satisfying P that blocks at least p points in general position, then there exists an input sequence of points in general position on which Greedy produces ℓ segments and matches at most a 2ℓ / (2ℓ + p) fraction of the 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

/-- Theorem 1.2: Equivalence between segment blocking numbers and Greedy competitive ratios. -/theorem greedy_matching_ratio_equiv_blocking_bounds    (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) :    (segment_blocking_bound_le P ℓ p →      ∀ pts : List (ℝ × ℝ), pts.Nodup → points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) →        (greedyMatching P pts).1.card = ℓ →        (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)) ≤ (2 * (ℓ : ℝ)) / (pts.length : ℝ)) ∧    (segment_blocking_bound_ge P ℓ p →      ∃ pts : List (ℝ × ℝ), pts.Nodup ∧ points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) ∧        (greedyMatching P pts).1.card = ℓ ∧        (2 * (ℓ : ℝ)) / (pts.length : ℝ) ≤ (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ))) := by  constructor  · intro hβ pts h_nodup h_gen h_card    exact greedy_matching_fraction_ge_of_blocking_le P hP ℓ p hβ pts h_nodup h_gen h_card  · intro hβ    exact greedy_matching_fraction_le_of_blocking_ge P hP ℓ p hβ
See it in the graphDiscuss this resultChallenge it