The Reluctant Semi-Algebraist<br> <em>Introduced by: Janos Pintz</em>
Presenter
December 1, 2012
Keywords:
- Ramsey theory
Abstract
By Ramsey's theorem, any system of n segments in the plane
has roughly logn members that are either pairwise disjoint or pairwise
intersecting. Analogously, any set of n points p(1),..., p(n) in the
plane has a subset of roughly loglogn 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 less than j less than 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.