Chromatic number of the hyperbolic plane

Question

A notorious problem in combinatorics is the following:

If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?

This number is sometimes called "the chromatic number of the plane" $\chi$ (since it is really a graph coloring problem on an infinite graph), and it is easily see that $ 4 \le \chi \le 7$ but these bounds have stood for quite a while.

It is natural to ask about coloring other metric spaces, and many people have. In particular, there are bounds known for the chromatic number of $\mathbb{R}^d$ for $d \ge 3$ (and some asymptotics as $d \to \infty$). Also there has been some work on coloring the two-dimensional sphere of radius $r$. (A nice reference for this kind of problem is Soifer's "The mathematical coloring book.")

My question is whether anyone has looked at the chromatic number of the hyperbolic plane. As with the sphere, there is a free parameter --- one could either take fixed curvature $-1$ and let the distance vary, or fix unit distance and let the constant negative curvature vary.

We might not expect to be able to solve this in general, since determining the chromatic number of the plane seems difficult, and now we have an infinite family of such problems. But we should be able to put bounds, and I am wondering what is known.

In particular, the following two questions come to mind. I would appreciate insights or pointers to references if these things have been previously studied.

(1) Is there a $5$-chromatic unit distance graph in the hyperbolic plane (for some constant negative curvature)?

(2) Is there an absolute upper bound on the chromatic number of the hyperbolic plane, that holds for all constant negative curvatures?

One might guess that the chromatic number of the hyperbolic plane is increasing as the constant negative curvature decreases, but if so does it grow without bound?

Answer 1

This does not really answer your questions, but I recently got a few results on the chromatic number of the hyperbolic planes. They are formulated by fixing the curvature and letting the distance vary, and I use the notation $\chi(\mathbb{H}^2,\{d\})$ for the chromatic number of the distance-$d$ graph on the hyperbolic plane with curvature $-1$.

1. for small $d$, $\chi(\mathbb{H}^2,\{d\})\leq 12$ (this can probably be improved, but maybe not easily to $7$),

2. for large $d$, $\chi(\mathbb{H}^2,\{d\})\leq \frac{4}{\ln 3} d + O(1)$.

The proofs can be found here: https://arxiv.org/abs/1305.2765, published in Geombinatorics Vol XXIV (3) 2015, pp. 117-134 (but the proof of the linear upper bound has some small issues, corrected with an improved bound in the subsequent work of Parlier and Petit https://arxiv.org/abs/1701.08648). All this is not difficult, and the paper raises more questions than it answers.

My impression is that the monotony of the chromatic number with $d$ seems reasonable, but is in fact a subtle issue; and I would rather bet on a negative answer to question (2) but not too high. All in all, these questions are probably incredibly difficult, because we have only very cumbersome tools to relate the geometry with the distance graph.

For the story: about one year after I read, liked and bookmarked your question, I had forgotten about it but read "Ramsey Theory, Today, and Tomorrow", and realized I could answer some questions asked in it by Johnson and Szlam. In the course of writing a paper from these answers, I investigated the case of the hyperbolic plane. After writing a first version I happened to look at my MO favorites, and saw your question again -- which is therefore cited in the paper (will there soon be a @mathoverflow in standard bibTeX definitions?)

Answer 2

Curiously, Soifer's Mathematical Coloring Book doesn't mention this variant, and I'd think he would have if something were known on it.

I don't know much more myself but I can at least relate it to a different known problem, Ringel's circle problem concerning the chromatic number of systems of circles, no three tangent at a single point, with pairs of tangent circles being required to have different colors. Ringel asked whether the chromatic number of these systems is bounded. There exist systems of circles where it is at least five; see e.g. https://ics.uci.edu/~eppstein/junkyard/tangencies/

For systems of circles, it doesn't matter whether you're using hyperbolic or Euclidean geometry — the circles are the same. So if you could find a hyperbolic point set whose unit distance graph required more than five colors then the system of circles of radius 1/2 centered at those points would improve the known lower bound on the circle problem. On the other hand if you could prove that Ringel's circle problem has a finite upper bound then so would the hyperbolic plane.

Answer 3

A new paper on the topic has appeared, and while it does not answer your question I find the result interesting enough to be mentioned in a separate answer.

DeCorte and Golubev prove there that for $r$ large enough ($r\ge 12$ suffices), the distance-$r$ graph of the hyperbolic plane with curvature $\kappa=-1$ has measurable chromatic number at least $6$ (here "measurable" means that the maps sending a point to its color is Lebesgue Measurable). It is known for long that the measurable chromatic point of the plane is at least $5$ (Falconer 1981), so the interesting point here is that the lower bound gets better for large distances (i.e. for very negative curvature, if one prefers to fix $r=1$ and let $\kappa$ run over $(-\infty,0)$).

Note that under the Solovay axioms, the measurable hypothesis can be dropped since all sets are Lebesgue measurable (but then we don't have the full axiom of choice, and thus no DeBruin-Erdös theorem: we cannot deduce that under the Solovay axioms there is a finite unit-distance graph whose chromatic number is at least $6$).