9
$\begingroup$

Which are the configrations $P\subset \mathbb{R}^2$ of points, such that the following property holds:

Property M (for Monochromatic): Every two-coloring of $\mathbb{R}^2$ contains a monochromatic copy of $P$.

(By "copy" we allow Euclidean motions and also scaling by a positive factor. By "monochromatic" we understand, as the name suggests, that all points in the copy have the same color)


Context:

In the question "Triangles whose vertices and center have all the same color", the point configurations "equilateral triangle" and "equilateral triangle with its center" are considered.

The question "Finding monochromatic rectangles in a countable coloring of $\mathbb{R}^2$" considered a slightly different problem: the colorings are countable and the rectangle is axis aligned (but its aspect ratio is not fixed).

If a complete classification of point configurations which satisfy Property M is too much to ask for, here are some perhaps simpler questions:

  1. What is the smallest example of a point configuration, which does not satisfy Property M?

  2. Can point configurations with Property M be arbitrarily large, perhaps even infinite (countable or not)?

  3. Given a point set $P$, is there an algorithm to decide whether it has Property M?

  4. Has this question been studied somewhere? (I am aware of some work, where one does not allow the scaling of the point set, e.g. Monochromatic triangles in two-colored plane

$\endgroup$
8
$\begingroup$

I think the best starting point are surveys by R. L. Graham; for example:

Euclidean Ramsey Theory, Handbook of discrete and computational geometry, 153–166, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997. (http://dl.acm.org/citation.cfm?id=285879)

Recent trends in Euclidean Ramsey theory, Discrete Mathematics Volume 136, Issues 1–3, 31 December 1994, Pages 119-127, https://doi.org/10.1016/0012-365X(94)00110-5

In particular, if you allow scaled copies, then every finite configuration $P$ has property $M$ (a theorem by Gallai and Witt). This should answer all the questions 1–4 for finite configurations $P$.

Also see this recent paper by J. F. Alm for a strenthening of Gallai's theorem (he shows that $2^{\aleph_0}$ monochromatic homothetic copies of $P$ exist):

https://arxiv.org/abs/1304.3154,

http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0005/0004/a003/index.html

$\endgroup$
5
$\begingroup$

Not an answer, just an illustration: Permit me to mention Ron Graham's challenge from 2003:


Conj2
EqTri
    (Figure from Computational Geometry Column 46.)
The citations here overlap with those referenced by Jan Kyncl.

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