The Endpoint Cardinality of Discrete Cube Skeleta
Information Theory
Summary
The authors find the smallest size of a special grid-like set of points that includes the outline of a cube (or its lower-dimensional skeleton) around every point in a given group of N points. They provide a formula for this minimum size, improving on previous work by Thornton, particularly for cases where part of the cube’s skeleton is considered (k ≥ 1). Their approach uses advanced mathematical tools like midpoint estimates and a version of Shearer's projection inequality, along with a new induction technique to handle scales effectively. For example, if you want a set containing the edges of squares around each of N points, it must have at least roughly N^(7/8) points.
Authors
Dean Menezes
Abstract
We determine the minimum order of a finite lattice set that contains a filled axis-parallel cube skeleton about every point of some $N$-point set of centers. For fixed integers $0\leq k<n$, the answer for $N$ centers is $N^{1-(n-k)/(2n^2)}$, up to constants depending on $n$ and $k$. Thornton proved every smaller exponent and gave a construction of this order; the endpoint lower bound was left open when $k\geq1$. Our proof combines a midpoint estimate, a labelled form of Shearer's projection inequality, and a strong induction that balances large and small radii without a dyadic pigeonhole loss. In particular, a lattice set containing a square boundary about each of $N$ centers has at least a constant times $N^{7/8}$ points.