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

Ramsey's theorem

Ramsey theory is a branch of combinatorics in which theorems typically state that any sufficiently large structure (e.g. a graph, a set of integers or a set of points in the plane) contains some large substructure (e.g. a complete graph, an arithmetic progression or a convex polygon). The starting point for this theory is Ramsey's theorem from 1930, stating that if the edges of a large enough graph are colored red and blue, there is a red clique of size $k$ or a blue clique of size $\ell$. The smallest size of a graph that guarantees this is the Ramsey number $R(k,\ell)$. The finiteness of the Ramsey numbers can be proved in an elementary way, but it is curious that the bounds given by simple arguments are almost the best that are known, despite that the upper and lower bounds are far from each other.

We will prove Ramsey's theorem, including its generalizations for multicolored graphs and hypergraphs. As corollaries we will prove Schur's theorem on the solvability of Fermat's equation $x^n+y^n=z^n, xyz\neq 0$ modulo any number, and the Happy Ending problem on finding convex polygons in an arbitrary set of points. We will also derive a lower bound due to Erdös for the Ramsey numbers. The bound is based on Erdös' probabilistic method, which has proved to be a very fruitful tool in combinatorics despite its simplicity. It is quite remarkable that the lower bound from 1947 that we are going to prove is the best one known up to a constant factor. Furthermore, so far all lower bounds that do not appeal to the probabilistic method (in particular constructive bounds) are considerably weaker than the probabilistic bound -- they do not even grow exponentially.