# Semi-algebraic Combinatorics

Janos Pach

## Affiliation:

EPFL, Lausanne and
Renyi Institute, Budapest

## Time:

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

## Venue:

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.