DMTCS Proceedings, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001

Font Size:  Small  Medium  Large

New Bounds for Hypercube Slicing Numbers

M. Reza Emamy-Khansary, Martin Ziegler


What is the maximum number of edges of the d-dimensional hypercube, denoted by S(d,k), that can be sliced by k hyperplanes? This question on combinatorial properties of Euclidean geometry arising from linear separability considerations in the theory of Perceptrons has become an issue on its own. We use computational and combinatorial methods to obtain new bounds for S(d,k), d ≤ 8. These strengthen earlier results on hypercube cut numbers.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional