Improved lower bound on hypercube edge slicing

The n-dimensional hypercube is a well-studied combinatorial object across many areas of mathematics and computer science. A hyperplane slices an edge of the hypercube if it contains exactly one interior point of the edge. It is natural to ask what is the minimum size of a hyperplane collection that slices every edge of the hypercube. Motivated by applications in theoretical computer science, this problem has attracted the attention of many researchers over the past 50 years. We show that Omega(n^{13/19-o(1)) hyperplanes are required, improving on the previous results by O’Neil, Yehuda—Yehudayoff, and Klein. We will discuss the main ideas that go into proving these lower bounds and some related questions.

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/