Rado's covering problem for cubes and balls: a semi-survey
For researchers in discrete geometry and covering theory, this work provides the best known asymptotic bounds for a classic problem, though the results are incremental improvements over existing techniques.
This semi-survey studies Rado's covering problem for cubes and balls in high dimensions, establishing that for d-dimensional cubes the optimal constant F(Q^d) lies between (e^{-1}+o(1))2^{-d}/(d log d) and 2^{-d}, while for d-dimensional balls F(B^d) is between (1+ε_d)3^{-d} and 2.447^{-d}, with the upper bound derived from sphere packing bounds.
What is the largest constant $c\in [0,1]$ with the property that every finite collection $\mathcal{C}$ of axis-parallel squares in the plane admits a disjoint sub-collection $\mathcal{S}$ occupying at least a fraction $c$ of the area covered by $\mathcal{C}$? This problem was first raised by T.~Radó in 1928, who was motivated by a classical covering lemma in real analysis due to Vitali. R.~Rado later generalized the problem from axis-parallel squares in the plane to homothetic copies of any given convex body $K$ in $\mathbb{R}^d$, where now we are looking for an optimal constant $F(K)$. Our utmost interest is for cubes and balls in the high-dimensional regime $d\rightarrow \infty$. The estimates that we currently have for cubes are much more precise than those for balls: namely if $Q^d$ is a $d$-dimensional cube, then \[ (e^{-1}+o(1))\frac{2^{-d}}{d \log{d}} \leq F(Q^d)\leq 2^{-d}, \] while denoting $B^d$ a $d$-dimensional Euclidean ball, then \[ (1+ε_d)3^{-d}\leq F(B^d)\leq 2.447^{-d}, \] where $ε_d>0$ vanishes exponentially fast as $d\rightarrow \infty$. The latter upper bound is obtained here by using the Kabatiansky--Levenshtein bound for the sphere packing problem.