Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Ramsey questions in discrete geometry
Speaker:Marek Elias
coming from:Charles University, Prague
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 15 May 2014
Duration:30 Minutes
Building:E1 4
Please note: New Room!
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

Name(s):Michael Kerber
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Michael Kerber, 04/27/2014 02:52 PM
  • Michael Kerber, 04/15/2014 03:56 PM -- Created document.