Colloquium: Janos Pach -- Towards a semi-algebraic combinatorics

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),..., 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 show that
"semi-algebraically" defined graphs and hypergraphs obey much nicer and stronger
combinatorial theorems than general ones.