segment_blocking_bound_ge
For a segment property P on Finset (Sym2 (ℝ × ℝ)) and natural numbers ℓ and p, segment_blocking_bound_ge P ℓ p asserts that there exists a finite family L of ℓ segments satisfying P with 2ℓ pairwise distinct endpoints and a disjoint finite point set S of at least p points such that the endpoints of L and S are jointly in general position and L blocks S under P.
Statement
def segment_blocking_bound_ge (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (ℓ p : ℕ) : Prop
- Defined in
- arXiv:2610.23130 Definition 1.1
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Built on 3
- 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…
- segment_endpointsGiven a finite set L : Finset (Sym2 (ℝ × ℝ)) of unordered pairs of points in ℝ × ℝ, segment_endpoints L is the finset of type Finset (ℝ ×…
- 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…
- Used by 2
- 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 ℓ…
- 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
Given a property P of finite sets of unordered pairs of points in ℝ², and natural numbers ℓ and p, segment_blocking_bound_ge P ℓ p asserts that there exist:
1. a finite set L of unordered pairs of points in ℝ² (Finset (Sym2 (ℝ × ℝ))), and
2. a finite set S of points in ℝ² (Finset (ℝ × ℝ)),
such that:
- L has cardinality ℓ,
- P L holds,
- the set of endpoints of pairs in L has cardinality 2 * ℓ (meaning all ℓ pairs in L are non-degenerate and pairwise disjoint),
- the set of endpoints of pairs in L is disjoint from S,
- the union of the endpoints of L and the set S is in general position (no three distinct points in this union are collinear in ℝ²),
- for every pair of distinct points u, v ∈ S, adding the pair {u, v} to L violates P (i.e., ¬ P (insert s(u, v) L)), and
- S has cardinality at least p (p ≤ S.card).
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
/-- Asserts that the blocking number β_P(ℓ) is at least p: there exists a family of ℓ disjoint segments satisfying P blocking at least p points in general position. -/ def segment_blocking_bound_ge (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (ℓ p : ℕ) : Prop := ∃ (L : Finset (Sym2 (ℝ × ℝ))) (S : Finset (ℝ × ℝ)), L.card = ℓ ∧ P L ∧ (segment_endpoints L).card = 2 * ℓ ∧ Disjoint (segment_endpoints L) S ∧ points_in_general_position (segment_endpoints L ∪ S : Set (ℝ × ℝ)) ∧ segments_block_points_prop P L S ∧ p ≤ S.card