Graph Theory – Monochromatic Triangles in Every Two-Coloring of the Plane

additive-combinatoricsgraph theoryramsey-theory

An old problem (possibly due to Erdős and Graham?): given a triangle $T$ and a two-coloring of the plane, does there necessary exist a monochromatic congruent copy of $T$? Here "monochromatic" means that all three vertices receive the same color. It is known that the answer depends on $T$.

There are several instances known where the answer is "yes". For example, an amusing exercise is to show that this holds if $T$ is a triangle with side lengths $1, \sqrt{3}, 2$. I believe Erdős and Graham gave infinite families of $T$ for which the answer is yes.

On the other hand, one can give a two-coloring of the plane so that there is no monochromatic triangle with side lengths $1, 1, 1$.

If I remember correctly, Erdős conjectured that there is always a monochromatic copy of $T$, except for the equilateral triangle which is the only exception.

(1) Does anyone know if there has been any recent progress on this conjecture?

(2) What I'd really like to know: what about the (degenerate) special case of a $1, 1, 2$ triangle? This question can be seen as a hypergraph analogue of the Hadwiger-Nelson problem, and suggests an interesting intersection of Euclidean Ramsey theory and additive combinatorics.

Best Answer

One recent development is the discovery of "zebra-like" colorings that avoid an equilateral triangle; before, it was unknown whether the only 2-coloring to avoid an equilateral triangle is the obvious alternating strip coloring. The relevant paper is http://arxiv.org/abs/math.CO/0701940.

In http://nucularpower.com/papers/monotriangle.pdf I show a 3-coloring that avoids the 1,1,2 triangle; I have been unable to find a 2-coloring that does so. It is easy to see (due to Soifer) that either a 1,1,1 or a 2,2,2 triangle imply that a 1,1,2 triangle exists (for 2 colors, again). It is also known that no two-coloring simultaneously avoids equilateral triangles of sides 1, 2, and 3.

The general conjecture is still wide open, as is the conjecture that 3 colors suffice to avoid any given triangle.

Edit, December 2016: I have updated the link to my note. In case the link becomes outdated again, the 3-coloring that avoids a degenerate triangle is just the coloring shown below, where the upper hexagon illustrates how boundaries are colored.

Hexagonal coloring that avoids a monochromatic degenerate triangle

Related Question