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

Question

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. Clearly $f(k) \le 7^k$, so $f(k)$ is well defined and is finite for every $k$.

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 \infty.$$ As pointed out in the comments, this follows from the fact that a square grid with $\sqrt{n} \times \sqrt{n}$ points only realizes $O \left( n / \sqrt{\log n} \right)$ distinct distances.

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

It was recently shown by Exoo and Ismailescu that $f(2) \ge 6$, but I'm not aware of any nontrivial lower bounds for $f(k)$ even for $k \ge 3$.

Any more information for small $k$ would be great, but I'm especially interested in the rate of growth as $k \to \infty$. Erdős apparently asked whether $f(k)$ grows only polynomially fast, and I am wondering whether this is still an open problem.

Answer 1

Erdos apparently asked whether $f(k)$ grows only polynomially fast, and I am wondering whether this is still an open problem.

This is very much an open problem. Other than using a set with few distinct distances, (which corresponds to an independent set in the graph), there have been no ideas to lower bound this problem asymptotically for large $k$. That is, the much weaker question of improving the lower bound to $$f(k)>Ck\sqrt{\log k}$$ for a constant $C > 1.4194\dots$ is open, where this constant is coming from distinct distances in subsets of the hexagonal lattice.

See Section 2 and Problem 4 of the Problems section of The Chromatic Number of $\mathbb{R}^n$ with Multiple Forbidden Distances.

Current state of knowledge

Notation: For a finite set of distances $A$, let $\chi(\mathbb{R}^{2},A)$ denote the chromatic number of the graph with vertex set $\mathbb{R}^2$ and edge set $E=\{(x,y)\in\mathbb{R}^2: \|x-y\|_2\in A\}.$ Define $$\overline{\chi}(\mathbb{R}^2,m):=\max_{A:\ |A|=m}\chi(\mathbb{R}^2,A).$$

Existing Bounds

The best lower bound I know of for $\overline{\chi}(\mathbb{R}^2,m)$ is $g^{-1}(m)$, where $g(n)$ is the minimum number of distinct distances among $n$ points in the plane, and it is an open problem if there exists a constant $C_1 > 1.4194\dots$ such that $$\overline{\chi}(\mathbb{R}^2,m)\geq C_1m\sqrt{\log m}(1+o(1)).$$ More generally, it is an open problem if there exists $C_2>1$ such that $\overline{\chi}(\mathbb{R}^2,m)>C_2g^{-1}(m)$. As for the upper bound, the best general upper bound is exponential, as you mentioned in your question.

Specific Distance Sets

However, for specific distance sets, we can give the order of growth almost exactly. Section 2 of The Chromatic Number of $\mathbb{R}^n$ with Multiple Forbidden Distances. discusses the specific case of $n=2$. The following Theorem is proven there, but was generally known to those interested in this problem:

Theorem: For a set of distances $\mathcal{D}=\{d_{1}<d_{2}<\cdots\}$, let $\mathcal{D}(m)=\{d_{1},\dots,d_{m}\}$ denote the $m$ smallest distances in $\mathcal{D}$. There exists a set of distances $\mathcal{D}_\Delta$ such that
$$\left|\chi(\mathbb{R}^{2},\mathcal{D}_{\Delta}(m))-1.75m\sqrt{\log m}\right|\leq 0.34 m\sqrt{\log m}(1+o(1)).$$

The specific distance set here is $$\mathcal{D}_\Delta=\{n\geq 1: \exists x,y\in\mathbb{Z} n=x^2+xy+y^2\}.$$ We have similar bound for the set $\mathcal{D}_{\square}=\{n\geq 1: \exists x,y\in\mathbb{Z} n=x^2+y^2\}.$ See section 2 of https://arxiv.org/abs/2205.12312 for more details.

Further improvements?

Both $\mathcal{D}_\Delta$ and $\mathcal{D}_\square$ are natural subsets of distances to consider, and this result suggests to me that to substantially improve the lower bound, one must work with relatively strange distance sets. I believe that $C m\sqrt{\log m}$ is close to the right answer, and the upper bounds are lacking.