Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.

What is $\chi(G)$?

(This is a variant of the Hadwiger-Nelson problem.)

  • $\begingroup$ Wow, it is a coloring problem in an infinite graph! The key point is the distribution relationship between R and Q. Interesting! $\endgroup$ – user39815 Feb 23 '15 at 8:38

By considering all the rational numbers on the $x$-axis we can see that we need at least countably many colors. This is also sufficient, that is the chromatic number of the rational-distances graph is countable. This is due to Erdos and Hajnal in the case of $\mathbb R^2$. They show that the rational-distances graph in the plane does not contain a copy of the complete bipartite graph $K(2,\omega_1)$, and that any such graph must have countable chromatic number.

P. Erdos and A. Hajnal, "On chromatic number of graphs and set systems", Acta Math. Hungar. 17(1966), 61-99.

The result was generalized to rational distances graphs in $\mathbb R^n$ by Peter Komjath. However, the previous method doesn't generalize since now the graph contains even a copy of $K(\omega, 2^\omega)$. Instead, Komjath uses a clever transfinite induction argument.

P. Komjath, "A decomposition theorem for $\mathbb R^n$" Proc. Amer. Math. Society (1994): 921-927.

  • $\begingroup$ Nice results! But I guess they use the axiom of choice, don't they? Do you know the answer in, say, Solovay axioms (or, if you prefer, when the colors are asked to be measurable sets)? $\endgroup$ – Benoît Kloeckner Feb 24 '15 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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