2025/10/18 by Lisa Sauermann, Zixuan Xu, Sauermann, Lisa +1
Computer Science · #Interconnection Networks and Systems #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.2510.16592
How many hyperplanes in ℝn are needed in order to slice every edge of the n-dimensional hypercube with vertex set \± 1\n? Here, we say that a hyperplane H⊆ ℝn slices an edge of the hypercube if it contains exactly one interior point of the edge. The problem of determining the minimum possible size of a collection of hyperplanes in ℝn, such that every edge of the hypercube is sliced by at least one of these hyperplanes, is more than 50 years old and has been studied by many researchers. We prove that, for sufficiently large n, at least Ω(n13/19log-32/19n) hyperplanes are needed, improving upon the best previous lower bound Ω(n2/3log-4/3n) due to Klein.