segment_crossing_graph
The 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 relative interiors intersect.
Statement
def segment_crossing_graph (L : Finset (Sym2 (ℝ × ℝ))) : SimpleGraph L- Defined in
- arXiv:2610.23130 Sec. 1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- segment_crossingTwo line segments in the plane, represented as unordered pairs of endpoints in Sym2 (ℝ × ℝ), cross if the intersection of their relative…
- Used by 10
- 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…
- blocking_card_three_of_three_crossing_pointsIf A, B, C are three pairwise distinct points of the plane, each lying in the relative interiors of the two segments of one of three…
- 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…
- triangle_free_blocking_ge_vertex_cover_of_le_threeFor every finite family of line segments L whose crossing graph is triangle-free and has vertex cover number at most 3, there exists a…
- triangle_free_blocking_ge_vertex_cover_of_le_oneFor 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…
- crossing_points_distinct_of_triangle_freeIf the crossing graph of L is triangle-free and A, B, C are interior intersection points of three star crossing pairs {gᵢ,hᵢ} (with the gᵢ…
- not_cliqueFree_three_of_crosses_crossing_pair_tfIf L is a triangle-free segment family and a new segment uv crosses both segments of a crossing pair in L (distinct from both), then…
- three_crossing_points_of_vertex_cover_threeIf a finite segment family has a triangle-free crossing graph and vertex cover number exactly 3, then there are three pairwise distinct…
- vertex_cover_three_extracts_star_pairsIf the crossing graph of a finite segment family has vertex cover number exactly 3, then one can extract three pairwise-distinct "cover"…
Read back from the Lean
Given a finite set L of unordered pairs of points in ℝ × ℝ (elements of Sym2 (ℝ × ℝ)), segment_crossing_graph L is the SimpleGraph on the vertex set L (the subtype of elements belonging to L) constructed via SimpleGraph.fromRel with the relation fun e₁ e₂ => segment_crossing e₁.1 e₂.1. Two vertices e₁, e₂ : L are adjacent if and only if e₁ ≠ e₂ and the open segment spanned by the endpoints of e₁ has a nonempty intersection with the open segment spanned by the endpoints of e₂.
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 crossing graph of a finite family of segments in ℝ². -/ def segment_crossing_graph (L : Finset (Sym2 (ℝ × ℝ))) : SimpleGraph L := SimpleGraph.fromRel (fun e₁ e₂ => segment_crossing e₁.1 e₂.1)