Stability for Hyperplane Covers

An almost $k$-cover of the hypercube $Q^n = \{0,1\}^n$ is a collection of hyperplanes that avoids the origin and covers every other vertex at least $k$ times. When $k$ is large with respect to the dimension $n$, Clifton and Huang asymptotically determined the minimum possible size of an almost $k$-cover. Central to their proof was an extension of the LYM inequality, concerning a weighting of hyperplanes. In this paper we completely characterise the hyperplanes of maximum weight, showing that there are $\binom{2n-1}{n}$ such hyperplanes. We further provide stability, bounding the weight of all hyperplanes that are not of maximum weight. These results allow us to effectively shrink the search space when using integer linear programming to construct small covers, and as a result we are able to determine the exact minimum size of an almost $k$-cover of $Q^6$ for most values of $k$. We further use the stability result to improve the Clifton–Huang lower bound for infinitely many choices of $k$ in every sufficiently large dimension $n$.

Authors

Publication Details

Journal
The Electronic Journal of Combinatorics
Published
2026-11-20
DOI
https://doi.org/10.37236/12528
Citations
2
Primary Topic
Advanced Combinatorial Mathematics
Type
article
Field-Weighted Citation Impact
1.22

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Stability for Hyperplane Covers

Wei-Hsuan Yu, Shagnik Das, Yen-chi Roger Lin, Valjakas Djaljapayan
2 citations
The Electronic Journal of Combinatorics
Advanced Combinatorial Mathematics
1.22
article

Stability for Hyperplane Covers

Wei-Hsuan Yu, Shagnik Das, Yen-chi Roger Lin, Valjakas Djaljapayan
article en
2 citations

Abstract

An almost $k$-cover of the hypercube $Q^n = \{0,1\}^n$ is a collection of hyperplanes that avoids the origin and covers every other vertex at least $k$ times. When $k$ is large with respect to the dimension $n$, Clifton and Huang asymptotically determined the minimum possible size of an almost $k$-cover. Central to their proof was an extension of the LYM inequality, concerning a weighting of hyperplanes. In this paper we completely characterise the hyperplanes of maximum weight, showing that there are $\binom{2n-1}{n}$ such hyperplanes. We further provide stability, bounding the weight of all hyperplanes that are not of maximum weight. These results allow us to effectively shrink the search space when using integer linear programming to construct small covers, and as a result we are able to determine the exact minimum size of an almost $k$-cover of $Q^6$ for most values of $k$. We further use the stability result to improve the Clifton–Huang lower bound for infinitely many choices of $k$ in every sufficiently large dimension $n$.

The Electronic Journal of CombinatoricsVol. 33(4)
Ministry of Science and Technology, Taiwan, National Science and Technology Council
Openalex Percentile: Top 31%
Advanced Combinatorial Mathematics
1.22
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon