A.M. Raigorodskii (Lomonosov Moscow State University and Moscow Institute of Physics and Technology) From combinatorial geometry to Ramsey theory Abstract: This talk consider problems on the boundary of combinatorial geometry and Ramsey theory. We start with two classical and closely connected problems: Borsuk's problem and the Nelson--Hadwiger problem. The first problem is to find the the least $t$ such that every bounded non-singleton set in ${\Bbb R}^n $ can be cut into $t$ parts of smaller diameter. The second problem deals with the chromatic number of Euclidean space, which is the smallest number of colors needed to paint all the points in ${\mathbb R}^n$ so that any two points separated by distance 1 receive different colors. The two problems admit graph theoretic interpretations that bring them close together. In the case of the Nelson--Hadwiger problem, one studies the chromatic number of a distance graph $G$, where $V(G)\subseteq {\mathbb R}^n$ and $E(G)$ consists of some pairs of vertices separated by distance $1$. In the case of Borsuk's problem, distance graphs are substituted by graphs of diameters. Here $V(G)$ is a (finite) set in ${\mathbb R}^n$ and vertices are joined by an edge if and only if the distance between them is the diameter of the set $V(G)$. The above interpretations not only provide a common language for both problems, but also they give rise to some important questions. In particular, classical questions of Ramsey theory may be naturally asked about distance graphs and graphs of diameters. We will first give a brief overview of the Borsuk and Nelson--Hadwiger problems.Then we will discuss Ramsey-theoretic aspects of both problems. For example, we will discuss graphs with small cliques and large chromatic numbers (small independence numbers) and graphs having both high girth and high chromatic number. |