Discrete Mathematics and Theoretical Computer Science Proceedings AA (DM-CCG), 2001, 155–1.pdfVIP

Discrete Mathematics and Theoretical Computer Science Proceedings AA (DM-CCG), 2001, 155–164 New Bounds for Hypercube Slicing Numbers M. Reza Emamy-Khansary1 and Martin Ziegler2† 1 PO Box 23355, Dept. of Math.,University of Puerto Rico,San Juan PR, 00931 2 Heinz Nixdorf Institute, University of Paderborn, 33095 Germany received February 4, 2001, revised April 10, 2001, accepted April 16, 2001. 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. Keywords: Hypercube cut number, linear separability, combinatorial geometry 1 Introduction Hyperplane H  d is said to slice the line segment L   λa  1 λ b : 0  λ  1 between vertices a b  d iff their intersection H  L is an interior point of this segment. Let    denote the d- d d d    d   d    d  1 dimensional hypercube, i.e., the geometric graph on vertex set d 1 1 with d d 2 undirected edges. It is obvious that the d hyperplanes d Hj  x  : xj  0 for j  1 ! d (1) slice all edges of . However M. Paterson [13] observed that for d  6 one can do better: 5 d sophisticatedly chosen