24
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Hearing this question I would be interested to know the following. If, for a given T, the answer is "yes" (i.e. if in any 2-coloring of the plane there exists a monochromatic copy of T) is this necessarily for a "finite reason"; i.e., must there then exist a finite 3-uniform hypergraph which can be embedded in the plane such that all its "edges" are triangles congruent to T, which is not 2-colorable? $\endgroup$ Jul 29, 2010 at 19:40
  • 6
    $\begingroup$ @James: Yes. There is a general compactness principle involved. See Graham, Rothschild, and Spencer's book Ramsey Theory, introduction. For all of these problems, including Hadwiger-Nelson, this is the case. I.e., if the chromatic number of the plane is 5, then there exists a finite unit distance graph that forces this. Similar statements hold for other problems of this type. $\endgroup$ Jul 29, 2010 at 19:49
  • 1
    $\begingroup$ @James: tinyurl.com/2f3ftzw is a link to an excerpt from Ramsey Theory on the Integers by Landman and Robertson, stating a (not fully general) version of the compactness principle. $\endgroup$ Jul 29, 2010 at 19:55
  • 2
    $\begingroup$ The De Bruijn–Erdős Theorem says that the chromatic number of an infinite graph (if it exists) is the maximum chromatic number of its finite subgraphs. Shelah and Soifer gave examples to suggest that the chromatic number of the plane might depend on set theoretic axioms. Here is an example of a coloring problem in the plane (with countably many colors), where the answer is equivalent to the Continuum Hypothesis: mathoverflow.net/questions/273/… $\endgroup$ Jul 29, 2010 at 21:32
  • $\begingroup$ Hey, Can anyone advice how to prove that for every two-coloring of the plain there will exist a triangle with with side lengths 1, √3 ,2 ? Thanx Itamar $\endgroup$
    – itamar
    Sep 10, 2010 at 20:15

1 Answer 1

19
$\begingroup$

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

$\endgroup$

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.