EUVIMEDEUVIMED entdecken
Crossref

Stability for Hyperplane Covers

Shagnik Das, Valjakas Djaljapayan, Yen-chi Roger Lin, Wei-Hsuan Yu

The Electronic Journal of Combinatorics · 20.11.2026 · 33 (4)

DOI: 10.37236/12528 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 20.11.2026. Verfasst von Shagnik Das und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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$.

Zitieren

APA

Das, S., Djaljapayan, V., Lin, Y. R., & Yu, W. (2026). Stability for Hyperplane Covers. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/12528

Vancouver

Das S, Djaljapayan V, Lin YR, Yu W. Stability for Hyperplane Covers. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/12528

BibTeX
@article{Das2026,
  author = {Das, Shagnik and Djaljapayan, Valjakas and Lin, Yen-chi Roger and Yu, Wei-Hsuan},
  title = {Stability for Hyperplane Covers},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {4},
  doi = {10.37236/12528}
}
Kostenlos starten →