When: Sunday, March 12, 10am
Where:
Schreiber 309
Speaker:
Ohad Klein, Hebrew University
Title:
Slicing all edges of an n-cube requires $n^{2/3}$ hyperplanes
Consider the $n$-cube graph in $\mathbb{R}^n$, with vertices $\{0,1\}^n$ and edges connecting vertices with Hamming
distance $1$.
How many hyperplanes are required in order to dissect all edges?
This problem has been open since the 70s. We will discuss this and related problems.
Puzzle: Show that n hyperplanes are sufficient, while sqrt(n) are not enough.