Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.

Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,0)$, $B = (0,\beta)$, $C=(-\alpha,0)$, $D = (0,-\beta)$, where $\alpha^2+\beta^2=1$ and $\alpha \notin \overline{\Bbb Q}$.

QUESTION: Is it possible to color $\Gamma$ with three colors so that no triangle (in $\Gamma$) is rainbow (has all three colors) and the colors of $A,B,C,D$ are $1,1,2,3$ respectively?

This question came up in my work in Discrete Geometry and is crucial to resolving an open problem. It is similar to many questions in Euclidean Ramsey Theory, but seems to be sufficiently different and perhaps has never been studied. Having spent many months on this, we are hoping someone can help.

NOTE: We do know some examples of such colorings of the plane, but none of them extend to the whole $\Bbb R^3$. Similarly, we don't know any such coloring where the rhombus $(A,B,C,D)$ as above is replaced by any $4$-cycle in $\Gamma$.

UPDATE (8/8/2020): The problem we wanted to solve using these $3$-colorings was later posted in this MO question, and was largely resolved in this paper. The connection between these two problems is explained in $\S5.4$. It's only in one direction, so the $3$-coloring problem remains open.

  • $\begingroup$ how does the triangle relate to ABCD? $\endgroup$
    – JMP
    Apr 14, 2015 at 11:30
  • 3
    $\begingroup$ @IgorPak : What do you know about the case where $\alpha$ is algebraic? $\endgroup$ Apr 14, 2015 at 17:14
  • 2
    $\begingroup$ @TimChow. As I say in the note, this is not an important condition - we will be happy with any $\alpha$. However, we can rule out some values such as $\alpha = 1/\sqrt{2}$ when (ABCD) is a square - it's easy to see that such coloring does not extend from (ABCD) to $\Bbb R^3$. We cannot rule out any transcendental values. $\endgroup$
    – Igor Pak
    Apr 14, 2015 at 17:23
  • 1
    $\begingroup$ In spite of your efforts, it is not clear what you ask of the coloring. My wording: Given R^3, A,B,C,D on a rhombus as stated, and start a three coloring with the assigned colors to the four points, can the coloring be extended to all of R^3 so that no unit equilateral triangle is rainbow? In particular, we need at least three circles around three edges to receive only two colors. I think this formulation avoiding Gamma is clear, since you are not asking for a proper graph coloring (neighboring vertices get different colors). Gerhard "Gamma Free For More Clarity" Paseman, 2015.04.14 $\endgroup$ Apr 14, 2015 at 18:05
  • 7
    $\begingroup$ @GerhardPaseman : Igor Pak's formulation seemed perfectly clear to me. Since he defined $\Gamma$, I thought it was obvious that "triangles" meant 3-cliques in $\Gamma$. In any case, your formulation is equivalent. $\endgroup$ Apr 14, 2015 at 22:58


Your Answer

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

Browse other questions tagged or ask your own question.