27
$\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.

Improve this question
$\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$
    – James Martin
    Commented 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$
    – Eric Tressler
    Commented 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$
    – Eric Tressler
    Commented 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$
    – Matthew Kahle
    Commented Jul 29, 2010 at 21:32
  • 1
    $\begingroup$ More generally it is known that, if T is any right triangle, then every 2-coloring of the plane contains a monochromatic copy of T. Soifer ("The Mathematical Coloring Book", Problem 40.10, p.491) credits it to Leslie Shader ("All right triangles are Ramsey in E^2!", JCTA 20 (1976), pp. 385-389, MR0409260). $\endgroup$
    – David Eppstein
    Commented Sep 10, 2010 at 21:53

1 Answer 1

Reset to default
22
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .