In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, such that $\bigcup_i A_i=\mathbb{R}^2$. Last week, de Grey strengthened this result, removing the requirement of measurability.

I would like a quantitative version of Falconer's result. For any measurable $A\subseteq \mathbb{R}^2$, define

$$ \overline\delta(A)=\limsup_{T\rightarrow\infty}\frac{\operatorname{vol}(A\cap[-T,T]^2)}{\operatorname{vol}([-T,T]^2)}. $$

Question: What is the supremum $m$ of $\overline\delta(\bigcup_i A_i)$ over all measurable $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$ that avoid unit distances?

I am interested in both lower and upper bounds.

Motivation: Polymath16 is attempting to find 5-chromatic unit-distance graphs with few vertices. By modifying a result of Pritikin (Lemma 1 here), one may show that every unit-distance graph with fewer than $1/(1-m)$ vertices is 4-colorable. As such, good estimates of $m$ would indicate how small our graphs can be.

Here's what we currently know:

  • The proof of Pritikin's Theorem 4 provides explicit $A_i$ to demonstrate $m\geq0.9174$.

  • Heule found a 5-chromatic unit-distance graph with 826 vertices, implying $m\leq 1-\frac{1}{826}$.

(Warning: Pritikin reports a lower bound of 0.919 after multiplying by 4 incorrectly. Also, it is not clear to me what his explicit construction is, as I don't have access to Croft's paper. I assume the construction uses $A'$ instead of $C'$.)

Presumably, there are other (linear programming?) approaches to obtain upper bounds. For related work, distance-avoiding sets in the plane seem to have received a bit of attention; see this survey.

  • 3
    Coloring a near penny packing (using pennies of diameter less than 1 and leaving enough space) probably gives the .919 lower bound. Anyone try substituting Reuleaux Triangles or other constant width object packings? Gerhard "Shaping Up A Lower Bound" Paseman, 2018.04.18. – Gerhard Paseman Apr 18 at 18:30

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.