Irregularities of distributions and extremal sets in combinatorial complexity theory
For researchers in discrepancy theory and combinatorial geometry, this offers a simpler proof of a known lower bound, but the result itself is not new.
The paper provides an elementary combinatorial proof that any set of n points in [0,1]^d has star-discrepancy at least c_{abs} d n^{-1}, matching the known lower bound. It also shows that point sets lacking a certain sub-box with many points on its boundary must have large star-discrepancy.
In 2004 the second author of the present paper proved that a point set in $[0,1]^d$ which has star-discrepancy at most $\varepsilon$ must necessarily consist of at least $c_{abs} d \varepsilon^{-1}$ points. Equivalently, every set of $n$ points in $[0,1]^d$ must have star-discrepancy at least $c_{abs} d n^{-1}$. The original proof of this result uses methods from Vapnik--Chervonenkis theory and from metric entropy theory. In the present paper we give an elementary combinatorial proof for the same result, which is based on identifying a sub-box of $[0,1]^d$ which has approximately $d$ elements of the point set on its boundary. Furthermore, we show that a point set for which no such box exists is rather irregular, and must necessarily have a large star-discrepancy.