# 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.

Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.

**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.

## Watch the video:

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.