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
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Apr 18 '18 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.