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$
$\endgroup$
1
asked Feb 23, 2015 at 8:19
-
$\begingroup$ Wow, it is a coloring problem in an infinite graph! The key point is the distribution relationship between R and Q. Interesting! $\endgroup$– user39815Commented Feb 23, 2015 at 8:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Feb 23, 2015 at 8:55
-
$\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$ Commented Feb 24, 2015 at 12:29