Geometry, Structure and Randomness in Combinatorics

One-dimensional Erdos-Szekeres-type theorems (joint work with Boris Bukh)

speaker: Jiri Matousek (Charles University, Prague)

abstract: We aim at better understanding of Ramsey functions for geometric Ramsey-type statements, as well as of algorithmic decidability of such statements. At present we have some answers for statements given by semialgebraic predicates dealing with points on the real line. We prove that for such predicates, the Ramsey function can be at most doubly exponential, and in some case it indeed is doubly exponential. We also exhibit an algorithm for deciding if a Ramsey property holds for such a predicate (or set of predicates).

<< Go back