A friend of mine came up with the following problem:

Let $\{X_1, X_2, ..., X_n\}$ be an arbitrarily finite partition of the unit square $[0, 1]^2$. Let $\{P_1, P_2, ..., P_m\}$ be a finite set of points in $[0, 1]^2$.
Can all the points $P_i$ be transformed through the same bijective affine transformation (rotation, translation, squeezing, scaling and shearing), so that all $P_i$ are contained in one of the $X_k$ ?

On a side note: Our professor told us to maybe ask somebody from the graph theory department. Could someone explain what the connection to graph theory is?

Edit: I would also be interested in ideas about the one-dimensional analogue.

  • $\begingroup$ By ‘partition’ do you mean into continuous regions, or do you allow perverse shapes that contain no finite neighborhoods? $\endgroup$ – Anton Sherwood Jun 7 '16 at 18:31
  • $\begingroup$ @AntonSherwood $X_1, X_2, ...X_n$ can be arbitrary disjoint subsets of $[0, 1]^2$ whose Union is $[0, 1]^2$. So any kind of perverse shape is allowed. $\endgroup$ – 0x539 Jun 7 '16 at 18:35
  • $\begingroup$ Obviously a partition will need to be somewhat perverse if it fails to accommodate a set of points because no $X_i$ can contain a ball. $\endgroup$ – Solomonoff's Secret Jun 7 '16 at 18:42

A different way of stating this result puts it squarely in the domain of Euclidean Ramsey theory:

Let $P = \{P_1, \dots, P_m\}$ be a finite set of points. Then, whenever the points in $[0,1]^2$ are colored by finitely many colors, one of the colors will contain an affine transformation of $P$.

In fact, a stronger result (except that we color all of $d$-dimensional space instead) is a theorem of Gallai (1943) and Witt (1951); see, for example, Theorem 11.5.3 here.

For any finite set $X \subset \mathbb R^d$, whenever $\mathbb R^d$ is colored by finitely many colors, one of the colors will contain a similar copy of $X$ (scaled, but identically oriented).

Superficially, this theorem does not appear to imply the result we want: just because $\mathbb R^2$ is guaranteed to contain a copy of $X$ doesn't mean the smaller set $[0,1]^2$ will. However, a standard compactness argument shows that whenever a result such as Gallai-Witt holds for colorings of $\mathbb R^2$, there is actually a finite set of points that cannot be colored without obtaining a scaled copy of $X$ - and we can always scale a finite set to fit inside the unit square.

To see this, let $T = \{1,2,\dots,n\}^{\mathbb R^2}$ be the set of all $n$-colorings of $\mathbb R^2$. Given the product topology, $T$ is compact by Tikhonov's theorem. For every set $S \subset \mathbb R^2$, let $T_S$ be the set of $n$-colorings of $\mathbb R^2$ that avoid a monochromatic scaled copy of $X$ that's contained in $S$. (In other words, the colorings of $S$ that avoid a copy of $X$, extended to colorings of all of $\mathbb R^2$ arbitrarily.)

Whenever $S$ is a finite set, $T_S$ is a closed subset of $T$: it is only specified on finitely many coordinates, so it's a finite union of an intersection of basic closed sets. If there is no finite set of points that forces a monochromatic scaled copy of $X$ when it's colored, then $T_S$ is nonempty for all finite sets $S$, and therefore the intersection $\bigcap_{S \text{ finite}} T_S$ is nonempty (by compactness of $T$). But this intersection is the set of all colorings of $\mathbb R^2$ that avoid a monochromatic scaled copy of $X$, so it must be empty by Gallai-Witt.

As a result, $T_S$ is already empty for some finite $S \subset \mathbb R^2$. Scale that $S$ to fit in $[0,1]^2$, and we have a proof that whenever $[0,1]^2$ is finitely colored, one color must contain a scaled copy of $X$.

(Compactness arguments like this one require the axiom of choice. In fact, one way to prove the Gallai-Witt theorem is to reduce it to the Hales-Jewett theorem. In that case, we have a finite point set to begin with, so we don't even need this argument, and don't need choice.)

  • $\begingroup$ Your definition of $T_S$ doesn't depend on $S$, as far as I can see. Is this a mistake? $\endgroup$ – 0x539 Mar 7 '18 at 19:06
  • $\begingroup$ It's absolutely a mistake. I've fixed it now. $\endgroup$ – Misha Lavrov Mar 7 '18 at 21:10

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.