The monotonicity of f-vectors of random polytopes

Abstract

Let $K$ be a compact convex body in ${\mathbb R}^d$, let $K_n$ be the convex hull of $n$ points chosen uniformly and independently in $K$, and let $f_{i}(K_n)$ denote the number of $i$-dimensional faces of $K_n$. We show that for planar convex sets, $E[f_0 (K_n)]$ is increasing in $n$.  In dimension $d \geq 3$ we prove that if $\lim_{n \to \infty} \frac{E[f_{d-1}(K_n)]}{An^c}=1$ for some constants $A$ and $c>0$ then the function $n \mapsto E[f_{d-1}(K_n)]$ is increasing for $n$ large enough. In particular, the number of facets of the convex hull of $n$ random points distributed uniformly and independently in a smooth compact convex body is asymptotically increasing. Our proof relies on a random sampling argument.