Slicing the Hypercube

Here's a neat result I heard about at virtual Dagstuhl last week, a new lower bound on the number of hyperplanes that cuts all the edges of a hypercube.

A n-dimensional hypercube has 2ⁿ vertices corresponding to the binary strings of length n. Edges are between two vertices that differ in exactly one bit, for a total of (n/2) 2ⁿ edges. Hypercubes played a large role in Hao Huang's recent proof of the sensitivity conjecture. 

A hyperplane is just a linear inequality in x₁,…,x_n the bits of the string corresponding to a vertex. An edge is cut if the inequality is true for one vertex and false for the other.

With n hyperplanes you can cut all the edges in two very different ways. 

• The hyperplanes x_i > 0 for each i. These are n orthogonal hyperplanes.
• The hyperplanes x₁+…+x_n > i for each i from 0 to n-1. These are n parallel hyperplanes.

Do you need n hyperplanes to cut all the edges? Mike Paterson found 5 explicit hyperplanes that cuts all the edges of a 6-dimensional hypercube (see survey by Mike Saks). Scaling that up means you need 5n/6 hyperplanes to cut an n-dimensional hypercube. That remains the best known upper bound.

For the lower bound, in 1971 Patrick O'Neil showed that any hyperplane can cut at most O(n^0.5) fraction of the edges (sharp by the hyperplane x₁+…+x_n > n/2). Thus you need at least O(n^0.5) hyperplanes which for 50 years was the best known bound.

Gil Yehuda and Amir Yehudayoff have given a new lower bound of O(n^0.57). The paper gives a O(n^0.51) bound but Yehudayoff said in a talk last week the bound has been improved.

Yehudayoff didn't go into much details in his 20 minute talk but the proofs uses geometry, probability and antichains. 

The result has some applications to complexity, namely you need at least n^1.57 wires in a depth-two threshold circuit for parity. But the main fun is the question itself, that we finally made progress and there is still a long way to go.