In how many ways a single hyperplane can cut a hypercube? Two "ways" are considered different, if the sets into which they divide vertices of the hypercube are different. So e.g. a line can cut 2-dimensional hypercube in 4 + 2 = 6 ways. 


Actually, all I need to know is whether the number of those possible cuts is polynomial or exponential with respect to the number of vertices of the hypercube.



Number of Hyper-cube cuts
Here is some handwaving which suggests that the growth rate is faster than polynomial.


For any cut of a d-cube, we can pair that with 2^d cuts of a parallel d-cube to get at least 2^d many cuts of a d+1-cube, which means that as d grows by 1, the number of cuts grows by a factor of n/2 where n is the number of vertices.


Gerhard "Ask Me About System Design" Paseman, 2012.02.29


