Small Boolean Sections in Alon-F\"uredi Covers

Abstract

Alon and F\"uredi proved that at least $n$ affine hyperplanes are required to cover $\{0,1\}^n\setminus\{\textbf{0}\}$ while avoiding the origin, and that this bound is sharp. We study how small the largest Boolean intersection among the hyperplanes can be in a cover attaining this minimum. Let $F(n)$ denote the minimum possible value of $\max_{H\in\mathcal H} |H\cap\{0,1\}^n|$ over all families $\mathcal{H}$ of $n$ affine hyperplanes covering $\{0,1\}^n\setminus{\mathbf{0}}$ and avoiding the origin. We give an explicit construction, proving that $F(n)=(1+o(1))\frac{2^n}{n},$ and hence asymptotically attain the averaging lower bound.