Theorem 1, p. 2 — for every k ≥ 1 some family of plane line segments has no three pairwise intersecting members and χ > k
ProvedTriangleFreeSegments.Probes.theorem_1chromatic-numberintersection-graphline-segmentsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1triangle-free
For every integer there is a finite family of pairwise distinct line segments in the plane , each with two distinct endpoints, such that
- no three segments of pairwise intersect, i.e. the intersection graph of (vertices the segments, edges the intersecting pairs) is triangle-free, and
- the chromatic number of that intersection graph exceeds :
This answers negatively Erdős's question whether families of segments in the plane are -bounded: triangle-free intersection graphs of segments can have arbitrarily large chromatic number.
Formalization Note Segments are closed segments in ℝ × ℝ, the family is indexed by Fin N, and the graph is the intersection graph of those actual segments (not an abstract graph). The chromatic number is Mathlib's chromaticNumber, valued in , and the conclusion is the literal .
Preamble
import Mathlib import Definitions.Def_TriangleFreeSegments_Probes_Setting
Formal statement
namespace TriangleFreeSegments.Probes
theorem theorem_1 (k : ℕ) (hk : 1 ≤ k) :
∃ (N : ℕ) (e : Fin N → (ℝ × ℝ) × (ℝ × ℝ)),
(∀ i, (e i).1 ≠ (e i).2) ∧
Function.Injective (fun i => seg (e i)) ∧
(interGraph (fun i => seg (e i))).CliqueFree 3 ∧
(k : ℕ∞) < (interGraph (fun i => seg (e i))).chromaticNumber := by sorry
end TriangleFreeSegments.Probes
Source
Pawlik et al., Triangle-free intersection graphs of line segments with large chromatic number, arXiv:1209.1595v5, p. 2, Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.