Geometric problems in Ramsey theory

In the previous post, we considered Ramsey theory for graphs. Graphs are however not the only combinatorial structures that are guaranteed to contain some regularity; another important example are sets of points in the plane or in a general Euclidean space. There are numerous theorems at the intersection of geometry and Ramsey theory, stating that such sets of points, whenever they are large enough, contain some geometrical structure. As examples of such results we consider the Erdös problem on the minimum number of distinct distances between $n$ points in the plane and the Hadwiger-Nelson problem on finding two points of the same color at unit distance when all points in $\mathbb{R}^2$ are colored with $k$ colors. We also give a more geometrical solution of the Happy Ending problem, which gives essentially the best known upper and lower bounds (the graph theoretic solution from the previous post gives very poor bounds).

The Happy Ending problem

The Happy Ending problem asks for the minimum number $N(k)$ of non-collinear points in the plane such that some $k$ of them always form a convex $k$-gon. In the 1935 paper of Erdös and Szekeres, A Combinatorial Problem in Geometry, three proofs were given for the finiteness of $N(k)$. The first one of them was based on the finiteness of the hypergraph Ramsey numbers. The third proof is based on König's lemma and does not give any concrete bounds for $N(k)$. The second proof, presented below, gives a better bound for $N(k)$.

Theorem 1 (Erdös and Szekeres). We have for all $k\geq 2$

$$\begin{eqnarray}N(k)\leq \binom{2k-4}{k-2}+1.\end{eqnarray}$$

Proof. Let $A_1,...,A_N$ be non-collinear points in the plane. Give these points cartesian coordinates by choosing $x$ and $y$ axes to be non-parallel to all the lines formed by the $A_i$. Call a sequence $A_{i_1},...,A_{i_k}$ of points increasing if the slopes of $A_{i_1}A_{i_2},A_{i_2}A_{i_3},...,A_{i_{k-1}}A_{i_k}$ form an increasing sequence, and call it decreasing if the slopes form a decreasing sequence. Note that any increasing or a decreasing sequence of $k$ points forms a convex $k$-gon. However, it is important to note that the vertices of a $k$-gon do not always form an increasing or decreasing sequence in any order; consider a regular hexagon for instance.

Define $f(k,\ell)$ as the smallest value of $N$ such that there is always either an increasing sequence of length $k$ or a decreasing sequence of length $\ell$. Trivially $f(k,2)=f(2,k)=2=\binom{k+2-4}{k-2}+1.$ We show that $f(k,\ell)\leq f(k-1,\ell)+f(k,\ell-1)-1$, and then $f(k,\ell)\leq \binom{k+\ell-4}{k-2}$ follows by induction from Pascal's triangle.

Consider the sequence of points $A_1,A_2,...,A_{f(k,\ell-1)}$. Either it contains an increasing sequence of $k$ points or a decreasing sequence of $\ell-1$ points. We may assume that the latter case holds, and let $A_{i_1}$ be the last point of (one of) the decreasing sequences of length $\ell-1$. Consider now the sequence $A_1,...,A_{i_1-1},A_{i_1+1},...,A_{f(k,\ell)},A_{f(k,\ell)+1}$. Again we may assume that there is a decreasing sequence of length $\ell-1$, and let $A_{i_2}$ be the end point of such a subsequence. Again remove $A_{i_2}$ from the sequence under consideration and add $A_{f(k,\ell)+2}$. Continuing in this way as long as possible, we get a sequence $A_{i_1},..,A_{i_{f(k-1,\ell)}}$ of distinct points such that each is an endpoint of a decreasing sequence of length $\ell-1$. Among these $f(k-1,\ell)$ points there is either a decreasing sequence of length $\ell$ or an increasing one length $k-1$. We may assume that the latter holds, and call the sequence $A_1',...,A_{k-1}'$. Let $A_{j_1},...,A_{j_{\ell-2}},A_1'$ be a decreasing sequence ending in $A_1'$ (it exists by assumption). Let the slope of $AB$ be $s(AB)$. By assumption, we have $$\begin{eqnarray}s(A_{j_1}A_{j_2})>...>s(A_{j_{\ell-2}}A_1')\end{eqnarray}$$

and

$$\begin{eqnarray}s(A_1'A_2')<...<s(A_{\ell-2}'A_{\ell-1}').\end{eqnarray}$$

If $s(A_{j_{\ell}-2}A_1')<s(A_1'A_2')$, we see that $A_{j_{\ell-2}-1},A_1',...,A_{k-1}'$ form an increasing sequence of length $k$, and if $s(A_{j_{\ell}-2}A_1')>s(A_1'A_2')$, then $A_{j_1},...,A_{j_{\ell-2}},A_1',A_2'$ form a decreasing sequence of length $\ell$. This proves the statement. ■

The upper bound obtained grows approximately like $4^k$, and as in the case of the Ramsey numbers $R(k,k)$, we find a lower bound of size approximately $2^k$. This is also due to Erdös and Szekeres, this time from 1961. A key ingredient in the proof, somewhat paradoxically, is actually showing that $\binom{2k-4}{k-2}$ is the largest size of a set not containing an increasing or a decreasing sequence of $k$ points (as already mentioned, there are many $k$-gons that do not form a monotonous sequence; take for example any $k$-gon with $k\geq 6$ that resembles a regular one). We follow these notes by Fernándes.

Lemma 2. Let $k$ and $\ell$ be positive integers and $\varepsilon>0$. There is a set $T$ of $\binom{k+\ell}{k}$ points in the plane without any increasing sequence of length $k+2$ or a decreasing sequence of length $\ell+2$ such that the slopes satisfy $|s(PQ)|<\varepsilon$ for any $P,Q\in T$.

Proof. We use induction on $k+\ell.$ The case $k=1$ is trivial: take $\ell+1$ points $A_1,...,A_{\ell+1}$ whose slopes $s(A_iA_{i+1})$ decrease but stay between $-\varepsilon$ and $\varepsilon.$ The case $\ell=1$ is symmetric. We use induction on $k+\ell.$ Let $T_1$ be a set with $\binom{k+\ell-1}{k-1}$ elements with slopes bounded by $\varepsilon$ and without any increasing sequences of length $k+1$ or decreasing sequences of length $\ell+2$. Similarly, let $T_2$ be a set of $\binom{k+\ell-1}{k}$ with slopes bounded by $\varepsilon$ and without any increasing sequences of length $k+2$ or decreasing sequences of length $\ell+1.$ Let $S_1'$ and $S_2'$ be homothetic copies of $S_1$ and $S_2$ such that $S_1$ belongs to the ball $B\left((0,0),\frac{\varepsilon}{100}\right)$ and $S_2$ belongs to the ball $B\left((\varepsilon,10\varepsilon),\frac{\varepsilon}{100}\right)$. Now the slope between any points, one of which is from $S_1'$ and the other from $S_2'$, is $\geq 2\varepsilon$. Let $I$ be an increasing sequence in $S_1'\cup S_2'$. If $I\subset S_1'$ or $I\subset S_2'$, then $|I|<k+2$, so we are done. Therefore, let $A_1,...,A_r$ be the points of $I$, with $A_1,...,A_s$ belonging to $S_1'$ and the rest belonging to $S_2'$. Now by construction $s(A_sA_{s+1})\geq 2\varepsilon$ but $s(A_{s+1}A_{s+2})\leq \varepsilon$. This is a contradiction, so $S_1'\cup S_2'$ has no increasing sequence of length $k+2$. Similarly if $A_1,...,A_r$ is a decreasing sequence of points such that $A_1,...,A_s$ belong to $S_2'$ and the rest belong to $S_1'$, we have $s(A_sA_{s+1})\leq -2\varepsilon$ but $s(A_{s+1}A_{s+2})\in [-\varepsilon,\varepsilon].$ The slopes are bounded by $100\varepsilon$, which can be taken to be arbitrarily small. ■

Now we are ready to prove the lower bound for $N(k)$.

Theorem 3 (Erdös and Szkeres). We have

$$\begin{eqnarray}N(k)\geq 2^{k-2}+1.\end{eqnarray}$$

Proof. We are going to construct a set of $2^{k-2}$ points without convex $k$-gons. Consider the vertices $P_1,...,P_{4k-4}$ of a regular $(4k-4)$-gon centered at the origin. Let $P_1,...,P_{k-1}$ be the vertices belonging to the quadrant bounded by the lines $y=x$ and $y=-x$. We define $k-1$ sets $T_0,...,T_{k-2}$ of points with the following properties.

(i) $T_i$ has $\binom{k-2}{i}$ points.

(ii) $T_i$ has neither an increasing sequence of length $k+2$ nor a decreasing sequence of length $k-i$.

(iii) For any $P,Q\in T_i$, the slope $s(PQ)$ is in $[-1,1]$.

These conditions can be satisfied in view of Lemma 2. Let $T_1',..,T_i'$ be homothetic copies of $T_0,...,T_{k-2}$ such that $T_i$ belongs to the ball $B\left(P_{i-1},\frac{1}{100k^2}\right)$, say. Now we have a set $S$ whose points are centered in small neighborhoods of $P_1,..,P_{n-1}$. We also have

$$\begin{eqnarray}|S|\leq \sum_{i\leq k-2}\binom{n-2}{i}=2^{k-2}.\end{eqnarray}$$

Let $C$ be a convex polygon whose vertices are from $S$. Let $i$ be the smallest index such that $C\cap T_i\neq \emptyset$, and let $j$ be the largest index such that $C\cap T_j\neq \emptyset.$ Let $P\in C\cap T_i,P'\in C\cap T_j$. Suppose $C\cap T_r$ contains two points, $Q$ and $Q'$ for some $i<r<j.$ The slope of $PP'$ is at least $1+\frac{1}{20k}$ , since the slope between $P_i$ and $P_{i+1}$ for $i\leq n-2$ is at least $1+\frac{1}{10k}$, say. On the other hand, $s(QQ')\leq 1$ by definition, so $s(QQ')$ must be negative. But then $s(QQ')\geq -1$, while $s(Q'P')\leq -1-\frac{1}{20k}$. Hence $S$ contains at most one point from each $T_r$, $i<r<j.$ Also the points in $C\cap T_i$ form a monotonous sequence, which clearly must be increasing. Similarly the points in $C\cap T_j$ form a decreasing sequence. By the definition of the sets $T_0,...,T_{k-2}$, this means that $C\cap T_i$ has at most $i+1$ elements, $C\cap T_j$ has at most $k-j-1$ elements, and $C$ has in total at most $(i+1)+(k-j-1)+(j-i-1)=k-1$ elements. The construction is now complete.

The bounds produced by the method above are very close to the best results known about $N(k)$. Indeed, Erdös and Szekeres conjectured that $N(k)=2^{k-2}+1$ always, but this remains open. For $k\leq 6$ this is known. The upper bound in turn has only been improved to $N(k)\leq \binom{2n-5}{n-2}+2$ by Tóth and Valtr.

Erdös distinct distances problem

We now turn to the Erdös distinct distances problem, which asks for the minimum number of distinct distances between $n$ points in the plane. This problem is another classical example of how hard simple-looking questions in Ramsey theory can turn out to be. Define $D(n)$ as the minimum number of distances among $n$ points. A trivial bound is $D(n)\leq \lfloor \frac{n}{2}\rfloor$, coming from a regular $n$-gon. Erdös was able to prove the following result in 1946.

Theorem 4 (Erdös). For $n\geq 3,$ we have

$$\begin{eqnarray}\sqrt{n-\frac{3}{4}}-\frac{1}{2}<D(n)<\frac{cn}{\sqrt{\log n}},\end{eqnarray}$$

where $c>0$ is a certain constant.

Proof. We start with the lower bound. Let $C$ be the convex hull of a set of $n$ points $P_1,...,P_n$ (the convex hull is the convex polygon whose vertices are from the set and which contains all the other points). Let $P_{a}$ be a vertex of it. Consider the $n-1$ distances $P_aP_i,a\neq a$. Let $K$ be number of different distances among these $n-1$ points, and let $N$ the maximum number of times a single distance occurs among these $n-1$ distances. Then $KN\geq n-1$, or $K\geq \frac{n-1}{N}$. By assumption, there exists $r$ such that $N$ of the distances $P_aP_i$ are equal to $r$. Now these points, say $Q_1,...,Q_N$ form a semicircle, because $C$ was convex. We may assume that $Q_1,...,Q_N$ are ordered in positive direction along the circle, so $Q_1Q_2<...<Q_1Q_N$. Hence $D(n)\geq \max\left\{\frac{n-1}{N},N-1\right\}$. The maximum is achieved when $N(N-1)=n-1$, and from this we easily solve for $N$.

The upper bound comes via an entirely different argument. Consider the points $(a,b)$ with integer points in the first quadrant of the plane, satisfying $0<a,b<\sqrt{n}$. The squared distance between any such points $(a,b)$ and $(c,d)$ is $(a-c)^2+(b-d)^2$, and hence the sum of two squares with $|a-c|,|b-d|< \sqrt{n}.$ Counting the number of integers in

$$\begin{eqnarray}\{n\leq y:n=a^2+b^2\,\, \text{with}\,\, a,b\in \mathbb{Z}\}\end{eqnarray}$$

is a simple sieve problem, because it is well-known that the set of prime divisors of the numbers $a^2+b^2$ is $p\equiv 1\pmod 4$ and $p=2$. Selberg's upper bound sieve (Theorems 1 and 5 from this post) gives

$$\begin{eqnarray}|\{n\leq y:n=a^2+b^2\,\, \text{with}\,\, a,b\in \mathbb{Z}\}|\ll y\prod_{p\leq y^{\frac{1}{3}}}\left(1-\frac{1}{p}\right)\ll \frac{y}{\sqrt{\log y}}\end{eqnarray}$$

by the prime number theorem in arithmetic progressions. Choosing $y=n$ the theorem follows. ■

The proof above is quite elementary, but Erdös was not able to improve his bounds. He did conjecture, though, that $D(n)\gg n^{1-\varepsilon}$ for any $\varepsilon>0$, so the lower bound should be far from the truth. In 1952, Moser improved Erdös' result to $D(n)\gg n^{\frac{2}{3}}$. Over the years, several improvements were given, until in 2010 Guth and Katz proved with a very complicated argument that $D(n)\gg \frac{n}{\log n}$, which settles the problem up to logarithmic factors.

The Hadwiger-Nelson problem

We consider lastly a problem that is of a bit different nature than the two previous ones, as here we color an uncountable number of points. The problem of Hadwiger and Nelson asks for the smallest number of colors such that in any coloring of the points of $\mathbb{R}^2$ there are two points at distance one from each other. The smallest such number is called the chromatic number of the plane and denoted by $\chi(\mathbb{R}^2)$. As with the previous problems, there are simple arguments that give the best known bounds.

Theorem 5. We have $4\leq \chi(\mathbb{R}^2)\leq 7$.

\textbf{Proof.} We start with the upper bound. Tessellate the plane with regular hexagons of side length $0.9$ parallel to the coordinate axes. We call a flower a collection of seven hexagon tiles such that one of them is adjacent to the others. The tessellation by hexagons of course induces a tessellation by flowers (after fixing one hexagon tile as a center of a flower). In each flower we color the central hexagon with color $1$ and the remaining hexagons with the colors $2,3,...,7$ such that the colorings of all the flowers are identical. The boundaries of the hexagons can be colored with any of the colors of one of the neighboring hexagons. Now the distance between two points with the same color is easily seen to be at least $0.9\cdot \sqrt{7}>1.$

The lower bound is given by the Moser spindle, a certain configuration of 7 points in the plane. Let $ABCD$ be a rhombus of side length $1$ and angles $\frac{\pi}{3}$ and $\frac{2\pi}{3}$, the angle at $A$ being the smaller one. We may say that $A$ is colored with $1$, $B$ with $2$, $C$ with $3$ and $D$ is colored with $1$ (otherwise we must use the fourth color). Rotate $ABCD$ around $D$ so that $D$ moves along a circle. Rotate it until $D$ is mapped to $D'$ with $DD'=1$. Let the images of $B$ and $C$ in this rotation be $B'$ and $C'$. Now $B'$ and $C'$ are colored with 2 and 3 in either order and $D'$ is colored with $1$. However, this is a contradiction as $|DD'|=1$. ■

The lower bound is due to the Moser brothers from 1961, while the upper bound was proved by Isbell in 1950. Determining the exact value of $\chi(\mathbb{R}^2)$ is an important problem in discrete geometry, but there are several guesses for what the answer could be. Erdös said in 1994 that ''almost surely'' $\chi(\mathbb{R}^2)\geq 5$. On the other hand, the answer may depend on the set of axioms for set theory, as we are dividing $\mathbb{R}^2$ into uncountable and possibly highly pathological sets.

One may ask more generally, what is the chromatic number of $\mathbb{R}^n$. The bounds known for it of course get weaker as $n$ grows, and the best ones known in general are

$$\begin{eqnarray}(1.239+o(1))^n\leq \chi(\mathbb{R}^n)\leq (3+o(1))^n.\end{eqnarray}$$

The upper bound was shown by Frankl and Wilson, and the lower one by Raĭgorodskiĭ. We consider a different generalization, moving from $\mathbb{R}^2$ to the rational plane $\mathbb{Q}^2$. Surprisingly, $\chi(\mathbb{Q}^2)$ is known and quite easy to determine. Moreover, it is much smaller than $\chi(\mathbb{R}^2)$.

Theorem 6 (Woodall, 1973). We have $\chi(\mathbb{Q}^2)=2$.

Proof. Obviously two colors are needed, so we must find a coloring of $\mathbb{Q}^2$ with two colors and no two points at distance $1$ apart. Let $\left(\frac{a}{b},\frac{c}{d}\right)$ we a point on the unit circle with $a$ and $b$ as well as $c$ and $d$ coprime. Then $a^2d^2+b^2c^2=b^2d^2.$ We have $b^2\mid a^2d^2$, so $b^2\mid d^2$ and hence $b\mid d.$ Similarly $d\mid b$, so $b=\pm d.$ Now $a^2+b^2=b^2$, and if $b$ is even, then $a$ and $b$ are both even, a contradiction. We conclude that if $(q_1,q_2)$ and $(r_1,r_2)$ are any rational points at distance one apart, then $q_1-r_1$ and $q_2-r_2$ are odd, meaning that their denominators are odd when written in reduced form.

We say that two pairs of rationals $(q_1,q_2)$ and $(r_1,r_2)$ are equivalent, and denote $(q_1,q_2)\sim (r_1,r_2)$, if $q_1-r_1$ and $q_2-r_2$ are odd. Clearly this relation is reflexive and symmetric. We show that it is transitive, so that it becomes an equivalence classes. Let $(q_1,q_2)\sim (q_3,q_4)\sim (q_5,q_6),.$ Now $q_1-q_3$ and $q_3-q_5$ are odd, so their sum $q_1-q_5$ is odd. Similarly $q_2-q_6$ is odd, so $(q_1,q_2)\sim (q_5,q_6)$.

Now $\mathbb{Q}^2$ is partitioned into equivalence classes by $\sim$. It suffices to color the points in one equivalence class, since if two points have distance one, they are equivalent. One equivalence class (the class of the point $(0,0)$) is the set of all odd rationals; we will color this class. Let the color of $\left(\frac{a}{b},\frac{c}{d}\right)$, where $\frac{a}{b}$ and $\frac{c}{d}$ are reduced and odd, be red if $a+c$ is odd and blue otherwise. Let $\left(\frac{a_1}{b_1},\frac{a_2}{b_2}\right),\left(\frac{a_3}{b_3},\frac{a_4}{b_4}\right)$ be odd reduced points at distance one apart. Then

$$\begin{eqnarray}(a_1b-3-a_3b_1)^2(b_2b_4)^2+(a_2b-4-a_4b_2)^2(b_1b_3)^2=(b_1b_2b_3b_4)^2.\end{eqnarray}$$

As $b_1,b_2,b_3$ and $b_4$ are odd, $a-1b_3-a_3b_1$ and $a-2b_4-a_4b_2$ have different parities. Hence $a_1-a_3$ and $a_2-a_4$ have different parities. This means that $a_1+a_3$ and $a_2+a_4$ have different parities, so it is not possible that $a_1+a_2$ and $a_3+a_4$ have the same parity. Hence $\left(\frac{a_1}{b_1},\frac{a_2}{b_2}\right)$ and $\left(\frac{a_3}{b_3},\frac{a_4}{b_4}\right)$ have different colors, so the proof is finished. ■