fitting points into partitions of a square

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.

Solution 1:

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.)