Classifying hyperplanes in hypercubes

O. Aichholzer and F. Aurenhammer

Abstract:

We consider hyperplanes spanned by vertices of the unit $d$-cube. We classify these hyperplanes by parallelism to coordinate axes, by symmetry of the $d$-cube vertices they avoid, as well as by so-called hull-honesty. (Hull-honest hyperplanes are those whose intersection figure with the $d$-cube coincides with the convex hull of the $d$-cube vertices they contain; they do not cut $d$-cube edges properly.) We describe relationships between these classes, and give the exact number of hull-honest hyperplanes, in general dimensions. An experimental enumeration of all spanned hyperplanes up to dimension eight showed us the intrinsic difficulty of developing a general enumeration scheme. Motivation for considering such hyperplanes stems from coding theory, from linear programming, and from the theory of machine learning.



Reference: O. Aichholzer and F. Aurenhammer. Classifying hyperplanes in hypercubes. SIAM Journal on Discrete Mathematics, 9(2):225-232, 1996. [IIG-Report-Series 408, TU Graz, Austria, 1995].