Semi-algebraic Combinatorics


Janos Pach


EPFL, Lausanne and
Renyi Institute, Budapest


Thursday, 18 February 2016, 14:30 to 15:30


  • AG-77

Abstract: By Ramsey's theorem, any system of n segments in the plane has roughly log $n$ members that are either pairwise disjoint or pairwise intersecting. Analogously, any set of n points $p(1),\cdots p(n)$ in the plane has a subset of roughly loglog $n$ elements with the property that the orientation of $p(i)p(j)p(k)$ is the same for all triples from this subset with $i<j<k$. (The elements of such a subset form the vertex set of a convex polygon.) However, in both cases we know that there exist much larger ``homogeneous'' subsystems satisfying the above conditions.

What is behind this favorable behavior? One of the common features of the above problems is that the underlying graphs and triple-systems can be defined by a small number of polynomial equations and inequalities in terms of the coordinates of the segments and points.

We discuss some structural properties of ``semi-algebraically'' defined graphs and hypergraphs, including Szemeredi-type partition theorems. Finally, we mention some joint results with Conlon, Fox, Sudakov, and Suk, establishing new Ramsey-type bounds for such hypergraphs.