Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source: original paper, printed pp. 533–534, Theorem 3 and Figure 3.

Statement

Let d>0d>0 and let T={t1,t2,t3}⊂R2T=\{t_1,t_2,t_3\}\subset\mathbb R^2. Every red-blue coloring of the plane contains a red pair at distance dd or a blue translate of TT.

Full proof

Assume there is no red pair at distance dd. Take the seven-point configuration WW whose dd-distance graph has independence number at most two.

For each i∈{1,2,3}i\in\{1,2,3\}, at most two points of ti+Wt_i+W are red, since a larger red subset would contain a pair at distance dd. Equivalently, there are at most two w∈Ww\in W for which ti+wt_i+w is red. The union of the three sets of bad choices of ww therefore has size at most six.

As ∣W∣=7|W|=7, some w∈Ww\in W is bad for none of the three indices. All of t1+w,t2+w,t3+wt_1+w,t_2+w,t_3+w are blue. They form a translate of TT, with its original orientation preserved.

This applies to every prescribed three-point set. It does not by itself force a four-point square or an arbitrary finite planar configuration; see the large-grid counterexample.

Bears on. Problem 214.