Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 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. http://www.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.

share|improve this answer

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: http://www-fourier.ujf-grenoble.fr/~bkloeckn/posts/2013-05-13-DistanceGraphs.html and the paper will appear on the arXiv soon. 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?)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.