Stability for hyperplane covers

MaRDI QIDQ6440116zbMATH OpenFDO

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

Publication date 13 June 2023

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

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 weighted count of hyperplanes. In this paper we completely characterise the hyperplanes of maximum weight, showing that there are $$ such planes. 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$.

This page was built for publication: Stability for hyperplane covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440116)