Playground Controls
Canvas Help:
- Click empty space to add points. Right-click points to delete.
Exact Unit Dist (80px ± 0.6)
Approx Unit Dist (± 2.5)
Hover/Drag Radar (80px)
Given $n$ points in the Euclidean plane, what is the maximum number of pairs $e$ that can be at distance exactly 1?
Here is the formal statement of a unit-distance graph and the Hadwiger-Nelson chromatic problem in Lean 4:
-- Lean 4 Formalization of Unit Distance Graphs and Hadwiger-Nelson Problem
import Mathlib.Analysis.Normed.Group.Basic
import Mathlib.Combinatorics.SimpleGraph.Basic
import Mathlib.Combinatorics.SimpleGraph.Coloring
open Metric Set SimpleGraph
/--
A unit distance graph in ℝ² has vertices as points in the plane,
and edges between vertices at distance exactly 1.
-/
def UnitDistanceGraph (V : Set (ℝ × ℝ)) : SimpleGraph V where
Adj u v := dist u.val v.val = 1
symm u v h := by
show dist v.val u.val = 1
rw [dist_comm]
exact h
loopless u := by
show dist u.val u.val ≠ 1
rw [dist_self]
norm_num
/--
The Hadwiger-Nelson Problem (Chromatic Number of the Plane):
The minimum number of colors needed to color the plane ℝ² such that
no two points at distance exactly 1 share the same color is at least 5
(proven by Aubrey de Grey in 2018) and at most 7.
-/
def ChromaticNumberOfPlane (χ : ℕ) : Prop :=
∃ (f : (ℝ × ℝ) → Fin χ), ∀ (p q : ℝ × ℝ), dist p q = 1 → f p ≠ f q
-- Aubrey de Grey's Theorem (2018)
theorem ChromaticNumberPlane_ge_five :
∀ (χ : ℕ), ChromaticNumberOfPlane χ → χ ≥ 5 := sorry