Hadwiger--Nelson Problem for Typical Norms

Abstract

The classical Hadwiger-Nelson problem asks for the chromatic number of the unit distance graph of the Euclidean plane. Over the years, this problem has been considered for a variety of other normed spaces, with higher-dimensional Euclidean space ℝ^d being perhaps the most natural and well-studied. Alon, Bucić, and Sauermann proved that, for a typical norm on ℝ^d, the chromatic number of the unit distance graph is at most 2^d. We improve this exponential bound to a linear one by showing that the chromatic number of a typical norm on ℝ^d is at most 2d and that this is tight. This shows a stark difference in the behavior compared to the Euclidean case, where there is an exponential lower bound. One of the key ingredients is a certain high-dimensional, matrix generalization of the Lonely runner conjecture, which also allows us to completely settle the so-called view-obstruction conjecture of Schoenberg from 1978 and a more recent covering-radius conjecture of Henze and Malikiosis.

P-curve: An improved solution for the single-facility location problem in two regions with ℓ_p- and ℓ_q-norms
Luis Franco, Francisco Velasco, Francisco J. Ortega-Irizo +1
arXiv1 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
A Proof of the Linear Hadwiger Conjecture
Sergey Norin, Raphael Steiner
arXiv4 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Hadwiger's Theorem on hyperbolic space
Jonas Knoerr
arXiv1 Sep 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
Beyond halfway to Hadwiger's conjecture
Chun-Hung Liu, Jason Luo
arXiv9 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Hadwiger's classification theorem on the sphere via signed orthoscheme decompositions
Martin Lotz
arXiv15 Sep 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{alon2026hadwigernelson,
  title = {{Hadwiger--Nelson Problem for Typical Norms}},
  author = {Noga Alon and Matija Bucić and James Davies},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.36220},
  eprint = {2609.36220},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36220},
}

RIS

TY  - UNPB
TI  - Hadwiger--Nelson Problem for Typical Norms
AU  - Noga Alon
AU  - Matija Bucić
AU  - James Davies
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.36220
UR  - https://arxiv.org/abs/2609.36220
AB  - The classical Hadwiger-Nelson problem asks for the chromatic number of the unit distance graph of the Euclidean plane. Over the years, this problem has been considered for a variety of other normed spaces, with higher-dimensional Euclidean space ℝ^d being perhaps the most natural and well-studied. Alon, Bucić, and Sauermann proved that, for a typical norm on ℝ^d, the chromatic number of the unit distance graph is at most 2^d. We improve this exponential bound to a linear one by showing that the chromatic number of a typical norm on ℝ^d is at most 2d and that this is tight. This shows a stark difference in the behavior compared to the Euclidean case, where there is an exponential lower bound. One of the key ingredients is a certain high-dimensional, matrix generalization of the Lonely runner conjecture, which also allows us to completely settle the so-called view-obstruction conjecture of Schoenberg from 1978 and a more recent covering-radius conjecture of Henze and Malikiosis.
ER  -

Abstract

Related

Cite