Talk information

Date: Sunday, March 12, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Ohad Klein (HUJI)
Title: Slicing all edges of an $n$-cube requires $n^{2/3}$ hyperplanes

Abstract:

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.