Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes
Author:
Preprint
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 $\widetilde{\Omega}(n^{2/3})$ are needed, which improves the previous bound of $\Omega(n^{0.51})$ by Yehuda and Yehudayoff.
Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- The plank problem for symmetric bodiesInventiones Mathematicae, 1991
- Hyperplane cuts of an n-cubeDiscrete Mathematics, 1971
- Ein Satz ber Untermengen einer endlichen MengeMathematische Zeitschrift, 1928