D. Menezes

Sharp Bounds for Discrete Cube Skeleta

Fix integers $0\leq k<n$. Let $F_{n,k}(N)$ be the least size of a finite set $B\subset\Z^n$ that contains a filled axis-parallel cube $k$-skeleton centered at each point of some $N$-point set. We prove that $F_{n,k}(N)$ has order $N^{1-(n-k)/(2n^2)}$, with constants depending only on $n$ and $k$. Thornton proved the upper bound and lower bounds with every smaller exponent; the endpoint lower bound was open for $k\geq1$. For square boundaries in $\Z^2$, the exponent is $7/8$. A midpoint count and Shearer's inequality handle large radii; induction in lattice cells handles small radii.