On the cut number problem for the 4, and 5-cubes

• Published in: Discrete Applied Mathematics 2021-11, Vol.303, p.66-75
• Main Authors: Emamy-K, M.R., Arce-Nazario, R.
• Format: Article
• Language: English
• Subjects: Computing time; Convex and discrete geometry; Cubes; Euclidean geometry; Euclidean space; Hypercube cuts; Hypercubes; Hyperplanes; Mathematical analysis
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2020.07.008

The hypercube cut number S(d) is the minimum number of hyperplanes in the d-dimensional Euclidean space that slice all the edges of the d-cube. The determination of S(d) in dimensions 5, 6, and 7, is one of the Victor Klee’s unresolved problems presented in one of his invited talks on problems from discrete geometry. The value of S(d) is unknown for d≥7, but for d≤3 it is trivial to show S(d)=d. In the late nineteen eighties, Emamy-K has shown S(4)=4 via two different proofs. More than a decade later, Sohler and Ziegler obtained a computational proof of S(5)=5 that took about two months of CPU computing time. From S(5)=5 it can be verified that S(6)=5. A short mathematical proof for d=5 remains to be a challenging problem that also leads one to the insight of the still open 7-dimensional problem. In this article we present a vertex coloring approach on the hypercube that gives a simplified proof for d=4 and also helps toward a short mathematical proof for d=5, free of computer computations.