New Lower Bounds For Essential Covers Of The Cube

An essential cover of the vertices of the $n$-cube $\{0,1{\}}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2}\rceil +1$ hyperplanes and showed that $\mathrm{\Omega }(\sqrt{n})$ hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the $n$-cube contains at least $\mathrm{\Omega }(n^{0.52})$ hyperplanes. In this paper, building on the method of Yehuda and Yehudayoff, we prove that $\mathrm{\Omega }\left(\frac{n^{5\mathrm{/}9}}{(\log n{)}^{4\mathrm{/}9}}\right)$ hyperplanes are needed.