# mg.metric geometry – Updated bounds or references for an old Erdős problem –– coloring the plane with multiple forbidden distances?

Define a graph $$G_1$$ where the vertices of $$G_1$$ are the points of the plane $$mathbb{R}^2$$, and a pair of vertices $$p, q$$ is connected by an edge if and only if the Euclidean distance $$d(p,q) =1$$. The Hadwiger–Nelson unit-coloring problem asks for the “chromatic number of the plane”: i.e. what is $$chi( G_1 )$$? The best known bounds are that $$5 le chi( G_1 ) le 7$$, with the lower bound improved from 4 to 5 in a breakthrough result by Aubrey de Grey in 2018.

Apparently Erdős asked about the following variant. Let $$S ={ d_1, d_2, dots, d_k }$$ be a set of positive numbers. Define $$G_S$$ with vertices corresponding to points in the plane, and edges corresponding to pairs of points at any distance $$d_1$$, $$d_2$$, …, or $$d_k$$.

Let $$f(k)$$ denote the maximum chromatic number $$max chi(G_S)$$ as $$S$$ ranges over all sets of $$k$$ positive numbers.

Roughly, how does $$f(k)$$ grow as $$k to infty$$?

According to Soifer (in The Mathematical Coloring Book), Erdős wrote that “it is not hard to see” that $$lim_{k to infty} frac{f(k)}{k} to 0,$$
although I have to admit that even this isn’t obvious to me immediately.

What are the best known upper and lower bounds on $$f(k)$$?

––Clearly $$f(k) le 7^k$$, so $$f(k)$$ is well defined and is finite for every $$k$$.

––It was recently shown by Exoo and Ismailescu that $$f(2) ge 6$$, but I don’t know of any nontrivial lower bounds for $$f(k)$$ for $$k ge 3$$.

I’m especially interested in the question of rate of growth. Erdős apparently asked whether $$f(k)$$ only polynomially fast.

Posted on Categories Articles