Consider the graph on $\mathbb{Q}\times\mathbb{Q}$ where two members of $\mathbb{Q}\times\mathbb{Q}$ form an edge if and only if their distance is $1$. Is that graph bipartite? If not, what is its chromatic number? (It is known to be $\leq 7$.)
$\begingroup$
$\endgroup$
2
asked Aug 29, 2023 at 12:24
-
3$\begingroup$ I think Theorem 7 of this source -- citeseerx.ist.psu.edu/viewdoc/… -- says this is a result of Woodall. $\endgroup$– Nick GillCommented Aug 29, 2023 at 12:29
-
3$\begingroup$ See here: math.stackexchange.com/questions/4115435/… $\endgroup$– Nick GillCommented Aug 29, 2023 at 12:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Yes, the chromatic number is $2$. This result is due to Douglas R. Woodall, “Distances realized by sets covering the plane”, J. Combinatorial Theory 14 (1973), 187–200. See also Alexander Soifer, The Mathematical Coloring Book (Mathematics of Coloring and the Colorful Life of Its Creators), Springer (2009), §11.2. See also my unpublished¹ note “The Hadwiger-Nelson problem over certain fields”, esp. ¶1.6.
- Because it turned out that (unbeknownst to me) most of the results contained therein were already obtained earlier in an (also unpublished) note by Eric Moorhouse, “On the Chromatic Numbers of Planes”, which is also relevant here.
-
1$\begingroup$ I this graph connected? If so, this would mean that we must partition the members of $\mathbb Q^2$ into "white" and "black" points, as on a chess board. Is there some way to tell which is which? $\endgroup$ Commented Aug 29, 2023 at 18:03
-
1$\begingroup$ @MichaelHardy No, the graph is not connected: it is the disjoint union of countably many classes, where $(x,y)$ and $(x',y')$ (in $\mathbb{Q}^2$) are in the same class when both $x-x'$ and $y-y'$ have $2$-adic valuation $v≥0$. (I think the classes thus divided are then connected.) Within the class of $(0,0)$, one color consists of those $(x,y)$ such that $x$ and $y$ have the same parity, and the other of those such that $x$ and $y$ have opposite parity, which is indeed like a chessboard. But you can independently choose the color mapping for each class. $\endgroup$– Gro-TsenCommented Aug 29, 2023 at 21:43
-
$\begingroup$ Is there a way to tell which pairs belong to the class to which $(0,0)$ belongs? $\endgroup$ Commented Aug 29, 2023 at 23:35
-
1$\begingroup$ @MichaelHardy I've just done so: the class of $(0,0)$ (which, again, I think is connected) consists of those $(x,y)$ such that $v(x)≥0$ and $v(y)≥0$ (where $v$ is the $2$-adic valuation), and, among those, one color consists of those such that $v(x)>0$ XOR $v(y)>0$ whereas the other consists of those such that $v(x)=0$ and $v(y)=0$ or both are $>0$. $\endgroup$– Gro-TsenCommented Aug 30, 2023 at 7:48
-