Small Boolean Sections in Alon-Füredi Covers

Abstract

Alon and Füredi proved that at least $n$ affine hyperplanes are required to cover $\{0,1{\}}^n\setminus \{\text{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 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.

11 pages

Topics & keywords