The minimum neighborliness of a random polytope

Abstract: Let

m u

be a probability distribution on

m a t h b b R^{d}

which assigns measure zero to every hyperplane and

S

a set of points sampled independently from

m u

. What can be said about the expected combinatorial structure of the convex hull of

S

? These polytopes are simplicial with probability one, but not much else is known except when more restrictive assumptions are imposed on

m u

. In this paper we show that, with probability close to one, the convex hull of

S

has a high degree of neighborliness no matter the underlying distribution

m u

as long as

n

is not much bigger than

d

. As a concrete example, our result implies that if for each

d

in

m a t h b b N

we choose a probability distribution

m u_{d}

on

m a t h b b R^{d}

which assigns measure zero to every hyperplane and then set

P_{n}

to be the convex hull of an i.i.d. sample of

n l e 5 d / 4

random points from

m u_{d}

, the probability that

P_{n}

is

k

-neighborly approaches one as

d o i n f t y

for all

k l e d / 20

. We also give a simple example of a family of distributions which essentially attain our lower bound on the

k

-neighborliness of a random polytope.

This page was built for publication: The minimum neighborliness of a random polytope