Nondegenerate hyperplane covers of the hypercube
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911485273309184 |
|---|---|
| author | Sauermann, Lisa Xu, Zixuan |
| author_facet | Sauermann, Lisa Xu, Zixuan |
| contents | We consider collections of hyperplanes in $\mathbb{R}^n$ covering all vertices of the $n$-dimensional hypercube $\{0,1\}^n$, which satisfy the following nondegeneracy condition: For every $v\in \{0,1\}^n$ and every $i=1,\dots,n$, we demand that there is a hyperplane $H$ in the collection with $v\in H$ such that the variable $x_i$ appears with a non-zero coefficient in the hyperplane equation describing $H$. We prove that every collection $\mathcal{H}$ of hyperplanes in $\mathbb{R}^n$ covering $\{0,1\}^n$ with this nondegeneracy condition must have size $|\mathcal{H}|\ge 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$ 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$-dimensional hypercube, in the case where all of the hyperplanes have bounded integer coefficients. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00773 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nondegenerate hyperplane covers of the hypercube Sauermann, Lisa Xu, Zixuan Combinatorics 05D40 We consider collections of hyperplanes in $\mathbb{R}^n$ covering all vertices of the $n$-dimensional hypercube $\{0,1\}^n$, which satisfy the following nondegeneracy condition: For every $v\in \{0,1\}^n$ and every $i=1,\dots,n$, we demand that there is a hyperplane $H$ in the collection with $v\in H$ such that the variable $x_i$ appears with a non-zero coefficient in the hyperplane equation describing $H$. We prove that every collection $\mathcal{H}$ of hyperplanes in $\mathbb{R}^n$ covering $\{0,1\}^n$ with this nondegeneracy condition must have size $|\mathcal{H}|\ge 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$ 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$-dimensional hypercube, in the case where all of the hyperplanes have bounded integer coefficients. |
| title | Nondegenerate hyperplane covers of the hypercube |
| topic | Combinatorics 05D40 |
| url | https://arxiv.org/abs/2507.00773 |