What is the minimum number of hyperplanes that slice all edges of the d-dimensional hypercube?

Introduction

It is our goal to close this gap! A first success, we were able to show [CCCG] that C(5)=5 and thereby solve an at least 15-year old open problem in Geometry.
More generally, we use both computational and combinatorial methods to investigate on so-called Slicing Numbers S(d,k), the maximum number of edges in the d-cube that k hyperplanes can slice; obviously C(d)>k iff S(d,k)<k*2^k-1. For instance, [Emamy2] strengthened his previous result   "C(4)=4"   to   "S(4,3)=30". Similarly in our recent work [DMCCG], we strengthen [CCCG]'s   "C(5)=5"   to   "S(5,4)=78".
The following two tables represent the present state of knowledge; high lighted entries are due to the author of this web-page.

d C(d) 1 1 2 2 3 3 4 4 5 <=5,   >=5 6 <=5,   >=5 7 <=6,   >=5 8 5 ... 7 d O(d1/2) .. O(d)

S(d,k) k=1 k=2 k=3 k=4 k=5 k=6 k=7 d=1 1 1 1 1 1 1 1 d=2 2 4 4 4 4 4 4 d=3 6 10 12 12 12 12 12 d=4 12 24 30 32 32 32 32 d=5 30 54 70 78 80 80 80 d=6 60 120 160 184...187 192 192 192 d=7 140 260 350...373 410...436 434...448 448 448 d=8 280 560 770..852 920..996 980..1024 1008..1024 1024 d

 

Interactive Challenge

With new computational techniques, we only recently found a new collection of 5 cuts in the 6-cube. Like Paterson's cuts, they are all homogeneous. Here is some further collection and another one.

• call a line segment [a,b] sliced by hyperplane H if their intersection is a point in the relative interior (a,b).
• Call a subset L of E a sliceable subset (SS) if some hyperplane slices all elements (edges) of L.
• Call it a maximal sliceable subset (MSS) if adding any edge from E makes it unsliceable.
• Call it k-sliceable if some set of k hyperplanes slice all its edges, i.e., iff L decomposed into k sliceable subsets.
• Call it maximal k-slicable (MkSS) if it is k-slicable but not any more after adding any edge from E.
  To the best of my knowledge, there is no characterization of this property by decomposition into maximal slicable subsets...
• A cut complex (CC) is the subgraph of the hypercube induced by exactly those vertices which lie in a common halfspace.
  More formally,   V'={-1,+1}^d n H⁺   for some oriented hyperplane H. In the sequel, the empty set V'={} is not considered a cut complex.

• reflections in direction j=1..d, i.e., mappings   u=(u₁,..,u_j,..,u_d) -> (u₁,..,-u_j,..,u_d)  
• permutation of dimensions
• any of the   2^d d!   combinations of the above.

• we performed extensive tests of our software,
• including experiments on numerical robustness.
• All previous results on cut numbers have been reproduced,
• such as the bounds on M(d) and
• complete lists of USRs for MSSs of E₃ and E₄ in [Emamy].
• For each considered dimension d=3..7, the size of these lists coincides with the corresponding "number of NPN-equivalence classes of threshold functions of d or fewer variables" listed in Table 2.3.2 of [Muroga].
• Furthermore, validy of Theorems 1-3 of [Emamy2] and
• of Paterson's (counter-) example could be confirmed algorithmically.
• Finally, we follow [Robertson] in disclosing all intermediate results, encouraging others to verify them and to repeat computations in their own implementations.

It remains to explain how we enumerate vertices and edges, i.e., to which element of V_d and E_d, respectively, the i-th bit corresponds to.
For vertices this is easy, since each v in V_d has has the form   v=( x₀,x₁,..,x_d-1 )   for x_i either 0 or 1,  i=0..d-1. This gives the correspondence canonically.

For E_d, note that each hypercube edge connects two vertices which differ in exactly one coordinate:

• that differing coordinate j between 0 and d-1
• the d-1 common coordinates, each either 0 or 1.

The following table compiles the sizes of one entry in bytes:

d	|Vd|	#bytes	|Ed|	#bytes
3	8	1	12	2
4	16	2	32	4
5	32	4	80	10
6	64	8	192	24
7	128	16	448	56

 

To exemplify the above explainations, here are the 14 USRs of CCs and of MSSs for E₄ shown graphically and their corresponding bitstring.
Least significat bit (LSB) is right, most significant bit (MSB) left. As USRs (unique symmetry representatives) we chose, among all equivalent sets, the smallest one with respect to lexicographical order, i.e., that whose bit string corresponds in binary respresentation to the least valued integer.

Name (according to [Emamy'86])	Cut Complex	induced MSS	USR of MSS
C1	0000000000000001	00000001000000010000000100000001	00000001000000010000000100000001
C2	0000000000000011	00000011000000110000001100000000	00000000000100010001000100010001
C3	0000000000000111	00000111000001110000001000000010	00000001000000010101010001010100
C4	0000000000001111	00001111000011110000000000000000	00000000000000000101010101010101
C5	0000000000011111	00011111000011100000010000000100	00000001000000010101010010101011
C6	0000000000111111	00111111000011000000110000000000	00000000000100010001000111101110
C7	0000000001111111	01111111000010000000100000001000	00000001000000010000000111111110
C8	0000000011111111	11111111000000000000000000000000	00000000000000000000000011111111
C8''	0000000101111111	01111110000110000001100000011000	00011000000110000100001010111101
C7'	0000000100111111	00111110000111000001110000010000	00000001011001111001100010011000
C8'	0000001100111111	00111100001111000011110000000000	00000000011001100110011001100110
C6'	0000000100011111	00011110000111100001010000010100	00000110000001100101011001010110
C4'	0000000000010111	00010111000001100000011000000110	00000110000101110001001000010010
C5'	0000000100010111	00010110000101100001011000010110	00010110000101100001011000010110