Pavel Valtr "Holes and islands in random point sets"

Pavel Valtr from Charles University in Prague will give the talk "Holes and islands in random point sets" on the labs' Big Seminar.

Abstract:

For $d\ge 2$, let $S$ be a finite set of points in $\mathbb{R}^d$ in general position. A set $H$ of $k$ points from $S$ is a $k$-hole in $S$ if all points from $H$ lie on the boundary of the convex hull $\mathrm{conv}(H)$ of $H$ and the interior of $\mathrm{conv}(H)$ does not contain any point from $S$. A set $I$ of $k$ points from $S$ is a $k$-island in $S$ if $\mathrm{conv}(I)\cap S=I$. Note that each $k$-hole in $S$ is a $k$-island in $S$.

For fixed positive integers $d, k$ and a convex body $K$ in $\mathbb{R}^d$ with $d$-dimensional Lebesgue measure 1, let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$. We show that the expected number of $k$-islands in $S$ is in $O(n^d)$. In the case $k=d+1$, we prove that the expected number of empty simplices (that is, $(d+1)$-holes) in $S$ is at most $2^{d-1}d!{n\choose d}$.

Our results improve and generalize previous bounds by Bárány and Füredi (1987), Valtr (1995), Fabila-Monroy and Huemer (2012), and Fabila-Monroy, Huemer, and Mitsche (2015). Joint work with Martin Balko and Manfred Scheucher.

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.