triangle_free_blocking_ge_vertex_cover_of_le_one
theoremverified
For every finite family of line segments L whose crossing graph has vertex cover number at most 1, there exists a point set P blocked by L with cardinality at least the vertex cover number.
Statement
theorem triangle_free_blocking_ge_vertex_cover_of_le_one
(L : Finset (Sym2 (ℝ × ℝ)))
(h_vc : (segment_crossing_graph L).vertexCoverNum ≤ 1) :
∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧
(segment_crossing_graph L).vertexCoverNum ≤ P.card- Source
- step towards triangle_free_blocking_ge_vertex_cover
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- segments_block_points_of_card_le_oneAny finite point set in ℝ² of cardinality at most 1 is vacuously blocked by any finite family of segments L under the triangle-free…
- segments_block_pointsA finite family of segments L blocks a finite point set P under the triangle-free crossing property if for every pair of distinct points…
- segment_crossing_graphThe crossing graph G(L) of a finite family of line segments L is the simple graph with vertex set L and edges between segments whose…
- Used by 1
- triangle_free_blocking_ge_vertex_cover_of_le_twoFor every finite family of line segments L whose crossing graph is triangle-free and has vertex cover number at most 2, there exists a…
Lean source view module on GitHub
/-- The triangle-free blocking lower bound holds when the crossing graph has vertex cover number at most 1. -/ theorem triangle_free_blocking_ge_vertex_cover_of_le_one (L : Finset (Sym2 (ℝ × ℝ))) (h_vc : (segment_crossing_graph L).vertexCoverNum ≤ 1) : ∃ P : Finset (ℝ × ℝ), segments_block_points L P ∧ (segment_crossing_graph L).vertexCoverNum ≤ P.card := by refine ⟨{(0, 0)}, segments_block_points_of_card_le_one L (by simp), by simp [h_vc]⟩