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

m a t h b b R^{n}

are needed in order to dissect all edges? We show that at least

w i d e t i l d e O m e g a (n^{2 / 3})

are needed, which improves the previous bound of

O m e g a (n^{0.51})

by Yehuda and Yehudayoff.

This page was built for publication: Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes