Nondegenerate hyperplane covers of the hypercube
Lisa Sauermann, Zixuan Xu · 2025
Read Nondegenerate hyperplane covers of the hypercube by Lisa Sauermann, Zixuan Xu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00773.txt.
Introduction
Lisa Sauermann and Zixuan Xu bound how few flat slices can cover every corner of a high-dimensional cube, under a fairness condition. A hyperplane cover assigns each vertex of the cube to a flat containing it. The nondegeneracy rule demands that every vertex sit on a slice that genuinely uses each of its coordinates, not one that ignores a variable. Their 2025 paper proves any such cover needs at least half the dimension in slices.
The bound is tight up to constant factors. It generalizes a hot recent problem about skew covers, where every slice must use every variable. As a bonus, the method pins down an old question about slices cutting every edge of the cube, for slices with small whole-number coefficients. Combinatorial geometers get two problems settled by one argument.
Catalog record
| CREATOR | Lisa Sauermann, Zixuan Xu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-00773
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nondegenerate hyperplane covers of the hypercube Thanks: University of Bonn, Germany. Email: [email protected] . Supported by the DFG Heisenberg Program. Thanks: Massachusetts Institute of Technology. Email: [email protected] Lisa Sauermann, Zixuan Xu Abstract . We consider collections of hyperplanes in ℝ n \mathbb{R}^{n} covering all vertices of the n n -dimensional hypercube { 0 , 1 } n \{0,1\}^{n} , which satisfy the following nondegeneracy condition: For every v ∈ { 0 , 1 } n v\in\{0,1\}^{n} and every i = 1 , … , n i=1,\dots,n , we demand that there is a hyperplane H H in the collection with v ∈ H v\in H such that the variable x i x_{i} appears with a non-zero coefficient in the hyperplane equation describing H H . We prove that every collection ℋ \mathcal{H} of hyperplanes in ℝ n \mathbb{R}^{n} covering { 0 , 1 } n \{0,1\}^{n} with this nondegeneracy condition must have size | ℋ | ⩾ n / 2 |\mathcal{H}|\geqslant n/2 . This bound is tight up to constant factors. It generalizes a recent result concerning the intensively studied skew covers problem, which asks about the minimum possible size of a hyperplane cover of { 0 , 1 } n \{0,1\}^{n} in which all variables appear with non-zero coefficients in all hyperplane equations. As an application of our result, we also obtain an essentially tight bound for an old problem about collections of hyperplanes slicing all edges of the n n -dimensional hypercube, in the case where all of the hyperplanes have bounded integer coefficients. 1. Introduction A collection of (affine) hyperplanes \mathcal{H} in \mathbb{R}^{n} is said to cover the vertices of the n -dimensional hypercube \{0,1\}^{n} if for every vertex v\in\{0,1\}^{n} , there exists a hyperplane H\in\mathcal{H} such that v\in H . It is natural to ask about the minimum possible size of a hyperplane collection \mathcal{H} satisfying this condition, i.e., to ask how many hyperplanes are needed to cover the n -dimensional hypercube. It turns out that without any further restrictions the answer to this question is trivial: Two hyperplanes suffice, for example one can take the two hyperplanes given by the equations x_{1}=0 and x_{1}=1 (and it is easy to see that one hyperplane is not enough to cover all vertices of the hypercube). However, questions of this type with various nondegeneracy conditions for \mathcal{H} have been studied intensively in the literature, see for example [ 1 , 6 , 7 , 11 , 13 , 16 , 17 , 19 , 20 ] . In particular, the problem of determining the minimum possible size of a skew cover of the n -dimensional hypercube received a lot of attention [ 3 , 11 , 12 , 16 , 18 , 21 ] . A collection \mathcal{H} of hyperplanes in \mathbb{R}^{n} covering \{0,1\}^{n} is called a skew cover of \{0,1\}^{n} , if for each hyperplane H\in\mathcal{H} , all of the n coordinate entries of the normal vector of H are non-zero. In other words, for each of the hyperplanes H\in\mathcal{H} , when writing down the corresponding hyperplane equation, all n variables must appear with non-zero coefficients. Geometrically, this means that all hyperplanes in \mathcal{H} are “skew” in the sense of not being parallel to any of the coordinate axes. The problem of estimating the smallest possible number of hyperplanes in a skew cover of \{0,1\}^{n} has been discussed extensively in a survey paper by Saks [ 16 , Problem 3.63] from 1993, and as explained in [ 16 , p. 241] , it is not hard to show that every skew cover of \{0,1\}^{n} must consist of at least \Omega(\sqrt{n}) hyperplanes. Yehuda and Yehudayoff [ 21 ] improved this lower bound to \Omega(n^{0.51}) via a reduction from this problem to a problem about hyperplane collections slicing all edges of the hypercube. Later, Klein [ 12 ] improved the lower bound for this slicing problem, implying a lower bound of \Omega(n^{2/3}/(\log n)^{4/3}) for the skew covers problem via the same reduction. Recently, the authors [ 18 ] observed that a result of Linial and Radhakrishnan [ 13 ] from 2005 implies that any skew cover of \{0,1\}^{n} must consist of at least n/2 hyperplanes. The same observation was independently obtained by Ivanisvili, Klein, and Vershynin [ 11 ] shortly afterwards. This lower bound of n/2 resolves the problem for skew covers up to constant factors. Indeed, it is easy to construct skew covers of \{0,1\}^{n} consisting of n hyperplanes. In this short note, we generalize the notion of a skew cover by considering the following weaker nondegeneracy condition: We consider hyperplane collections \mathcal{H} with the condition that for every v\in\{0,1\}^{n} and every coordinate direction i=1,\dots,n , there exists a hyperplane H\in\mathcal{H} with v\in H such that the i -th coordinate of the normal vector of H is non-zero. This condition means that when expressing H via its hyperplane equation \langle a,x\rangle=b (where a\in\mathbb{R}^{n} is the normal vector of H , and b\in\mathbb{R} ), then the variable x_{i} appears with a non-zero coefficient in this equation. Geometrically, the condition on \mathcal{H} can be rephrased as saying that for every vertex v\in\{0,1\}^{n} of the hypercube, and every hypercube edge e incident to v , there exists a hyperplane H\in\mathcal{H} that contains v but not the entire edge e . We show the following lower bound for the number of hyperplanes in such a nondegenerate cover. Theorem 1.1 . Let \mathcal{H} be a collection of hyperplanes in \mathbb{R}^{n} satisfying the following condition: for every v\in\{0,1\}^{n} and every i=1,\dots,n , there exists a hyperplane H\in\mathcal{H} through v such that the i -th coordinate of the normal vector of H is non-zero. Then we must have |\mathcal{H}|\geqslant n/2 . Note that the bound of n/2 is tight up to constant factors. Indeed, for any n\geqslant 2 , one can consider the n hyperplanes given by the equations x_{1}+\dots+x_{n-1}-(n-1)x_{n}=0 and x_{1}+\dots+x_{n}=t for t=1,\dots,n-1 . Also note that Theorem 1.1 generalizes the above-mentioned lower bound results for skew covers, since every skew cover of \{0,1\}^{n} automatically satisfies the condition in Theorem 1.1 . As mentioned above, the problem of determining the minimum size of a skew cover of the hypercube \{0,1\}^{n} is related to the problem of determining the minimum number of hyperplanes required to slice every edge of the hypercube. We say that a hyperplane H in \mathbb{R}^{n} slices an edge of the n -dimensional hypercube if H contains exactly one interior point of the edge. Equivalently, when denoting the two endpoints of the edge as v,v^{\prime}\in\{0,1\}^{n} , and writing H=\{x\in\mathbb{R}^{n}\mid\langle a,x\rangle=b\} , the hyperplane H slices the edge vv^{\prime} if \langle a,v\rangle-b and \langle a,v^{\prime}\rangle-b are both non-zero and have different signs Now, it is natural to ask how many hyperplanes in \mathbb{R}^{n} are needed in order to slice every edge of the hypercube. More formally, what is the minimum possible size of a collection \mathcal{H} of hyperplanes in \mathbb{R}^{n} such that every edge of the n -dimensional hypercube [0,1]^{n} is sliced by at least one hyperplane in \mathcal{H} ? This has problem has attracted the attention of many researchers over the past 50 years [ 2 , 3 , 8 , 9 , 10 , 12 , 14 , 15 , 16