Department of
Applied
Mathematics

On Erdős-Szekeres Type Questions in R^d

Manfred Scheucher

TU Berlin

Abstract

A generalization of the classical Erdős-Szekeres Theorem to higher dimensions asserts that every sufficiently large set S in R^d in general position contains a subset of k points in convex position - this structure is commonly known as k-gon. When asking for a subset of k points such that its convex hull does not contain other points from S - commonly known as k-hole - it is known that the answer is not always affirmative: For every dimension, there exist arbitrarily large point sets with only constant-sized holes. Besides the existence of k-gons and k-holes, also their quantities have been investigated extensively in the last decades. In this talk I present some brand new bounds on the number of k-holes in higher dimensions.

This is joint work with Martin Balko and Pavel Valtr, research is in progress.