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.