Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes

Abstract

Consider the $n$-cube graph with vertices $\{-1,1{\}}^n$ and edges connecting vertices with hamming distance $1$. How many hyperplanes in ${\mathbb{R}}^n$ are needed in order to dissect all edges? We show that at least $\tilde{\Omega }(n^{2/3})$ are needed, which improves the previous bound of $\Omega (n^{0.51})$ by Yehuda and Yehudayoff.

arXiv comment10 pages; A few inaccuracies corrected