Lower bounds on the minimal dispersion of point sets via cover-free families

Abstract

We elaborate on the intimate connection between the largest volume of an empty axis-parallel box in a set of $n$ points from $[0,1{]}^d$ and cover-free families from the extremal set theory. This connection was discovered in a recent paper of the authors. In this work, we apply a very recent result of Michel and Scott to obtain a whole range of new lower bounds on the number of points needed so that the largest volume of such a box is bounded by a given $\epsilon$. Surprisingly, it turns out that for each of the new bounds, there is a choice of the parameters $d$ and $\epsilon$ such that the bound outperforms the others.

References in corpus (1)

• A tight lower bound on the minimal dispersion