Improved lower bound on hypercube edge slicing
Improved lower bound on hypercube edge slicing
-
Zixuan Xu, Princeton
Fine Hall 224
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 potentially some recent developments found by GPT.