Pavel Valtr “Holes and islands in random point sets”

July 30, 2020
19.00 MSK (UTC +3)

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.

The talk will be held in zoom
Meeting ID: 279-059-822
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.