Paperlane

no. 9 · Thursday 5 November 2026

On Diameter Graphs Problems: A proof of Brass's Conjecture

Gyivan Lopez-Campos

math.CO · 16 pp

Abstract

The diameter graph of a finite set $S\subset\mathbb{R}^d$ has vertex set $S$ and two points are adjacent when their distance equals $\operatorname{diam} S$. In this paper we study the following question: given $k$ and $d$, is there a constant $c=c(k,d)$ such that from every finite point set $S\subset\mathbb{R}^d$ one can remove at most $c$ points so that the subgraph of the diameter graph induced by the remaining points is $k$-colorable? Brass conjectured that such a constant exists for $d=3$ and $k=3$. We prove this conjecture by showing that at most one point needs to be removed. We also answer a question of Dol'nikov, showing that for every positive integer $m$, there exist a finite point set $S\subset\mathbb{R}^3$ in which every subset of smaller diameter has less than $(|S|-m)/2$ points.

comments
16 pages, 4 figures
fields
Combinatorics, Metric Geometry
pdf ↗ page arXiv:2611.05631 ↗