AFTD Auto-Formalizing Theoretical Domains

greedyMatching

def

Given a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P across pts starting from the empty matching ∅ : Finset (Sym2 (ℝ × ℝ)) and empty unmatched list [].

Statement

noncomputable def greedyMatching (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (pts : List (ℝ × ℝ)) :
    Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ)
Defined in
arXiv:2610.23130, Section 1
Verified
22 Oct 2026
Axioms
none listed
Built on 1
  • greedyStepGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2…
Used by 5
  • 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 ℓ…
  • not_greedy_fraction_le_of_blocking_geThe statement greedy_fraction_le_of_blocking_ge is false: The statement is false as written; a machine-checked refutation is provided.…
  • 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…
  • greedyMatching_nilFor every predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in ℝ × ℝ, greedyMatching P [] equals the…

Read back from the Lean

greedyMatching is a definition taking a predicate P on finite sets of unordered pairs of points in ℝ² (P : Finset (Sym2 (ℝ × ℝ)) → Prop) and a list of points pts : List (ℝ × ℝ), returning a pair (M, U) : Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ). It is defined as the left-fold of greedyStep P over pts starting with the accumulator (∅, []).

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

/-- The greedy online geometric matching algorithm on an input sequence of points. -/
noncomputable def greedyMatching (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (pts : List (ℝ × ℝ)) :
    Finset (Sym2 (ℝ × ℝ)) × List (ℝ × ℝ) := pts.foldl (greedyStep P) (∅, [])
See it in the graphDiscuss this resultChallenge it