MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Ramsey questions in discrete geometry

Marek Elias
Charles University, Prague
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 15 May 2014
13:00
30 Minutes
E1 4
022
Saarbrücken

Abstract

Ramsey theory contains many theorems of a similar form: in every

sufficiently large structure we can find a homogeneous substructure of
nontrivial size. Actually, one of the first results in this field was
in geometric context. In 1935 Erdos and Szekeres proved that among n^2
points in a plane n of them form a monotone subset, and that every set
of 2^n points contains an n-point convex or an n-point concave subset.
Recently, there was a progress in this area concerning Semialgebraic
predicates. Conlon, Fox, Pach, Sudakov, and Suk showed that every set of
twr_k(n^c) points in R^d equipped with a (k+1)-ary semialgebraic
predicate contains an n-point set homogeneous according to this
predicate. They also constructed a set S of twr_k(cn) points in
dimension 2^{k-2} and a (k+1)-ary semialgebraic predicate P such that
there is no P-homogeneous subset of S of size n+1. In this talk we
present a result with Matousek, Roldan-Pensado, and Safernova which
lowers the dimension needed for this construction, as well as bounds and
constructions for some specific predicates e.g. Order type.

joint work with J. Matousek, E. Roldan-Pensado, and Z. Safernova

Contact

Michael Kerber
--email hidden
passcode not visible
logged in users only

Michael Kerber, 04/27/2014 14:52
Michael Kerber, 04/15/2014 15:56 -- Created document.