TOPICS
Search

Hypercube Hyperplane Cover


A hypercube hyperplane cover is a multiset of hyperplanes covering specified vertices of a hypercube. An almost k-cover of Q_n={0,1}^n avoids the origin and covers every other vertex at least k times. Let f(n,k) be the minimum number of hyperplanes in such a cover, counting multiplicity, where n and k are positive integers.

Alon and Füredi (1993) proved that f(n,1)=n. More generally, Clifton and Huang (2020) proved

 f(n,k)>=[kH_n],
(1)

where H_n=sum_(j=1)^(n)1/j is a harmonic number and [x] is the ceiling function. This bound is asymptotically tight as k->infty for fixed n.

The relevant weighting assigns weight 1/(t(n; t)) to a vertex with t>=1 coordinates equal to 1, where (n; t) is a binomial coefficient. The weight w(h) of a hyperplane h avoiding the origin is the sum of the weights of the vertices it contains. Clifton and Huang (2020) proved w(h)<=1. Das et al. (2026) characterized equality. For the normalization

 h={x in R^n:sum_(i=1)^nc_ix_i=1},
(2)

the weight equals 1 iff every c_i is an integer at most 1 and sum_(i=1)^(n)c_i>=1. There are exactly (2n-1; n) such hyperplanes. All other hyperplanes avoiding the origin have weight at most 1-1/n. More generally, if w(h)>1-r/n for a positive integer r, then at most r-1 of the coefficients exceed 1 and at most 2r^2-1 are not integers.

Das et al. (2026) also proved that

 f(6,k)=[(49k)/(20)]
(3)

for k>=16 provided k≢11  (mod20) and k not in {22,42,62,82,102}. For every sufficiently large n, there are infinitely many k for which f(n,k)>=[kH_n]+1.


See also

Hypercube, Hyperplane, Set Cover Problem

Explore with Wolfram|Alpha

References

Alon, N. and Füredi, Z. "Covering the Cube by Affine Hyperplanes." Europ. J. Combin. 14, 79-83, 1993. https://doi.org/10.1006/eujc.1993.1011.Clifton, A. and Huang, H. "On Almost k-Covers of Hypercubes." Combinatorica 40, 511-526, 2020. https://doi.org/10.1007/s00493-019-4221-y.Das, S.; Djaljapayan, V.; Lin, Y.-C. R.; and Yu, W.-H. "Stability for Hyperplane Covers." Elec. J. Combin. 33, P4.37, 2026. https://doi.org/10.37236/12528.

Cite this as:

Weisstein, Eric W. "Hypercube Hyperplane Cover." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HypercubeHyperplaneCover.html

Subject classifications