# Number of Hyper-cube cuts

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.

-
Surely it grows exponentially: for $d=8$ it is already beyond $10^{12}$. The number of threshold functions is about twice the number of slicing hyperplanes, so you could look at that literature for a citation, e.g., S. Yajima, T. Ibaraki "A lower bound of the number of threshold functions" IEEE Trans. Comput., EC-14 (1965), pp. 926–929 (which I cannot access). –  Joseph O'Rourke Feb 29 '12 at 16:55
Oh, I see from Gerhard's comment that I misread: I meant the number grows exponentially with the dimension $d$. –  Joseph O'Rourke Feb 29 '12 at 18:36
It may be of order $2^{n^2}$ which would be $v^{\log{v}}$ –  Aaron Meyerowitz Feb 29 '12 at 18:43
This doesn't answer the question, but has some references and another term: oeis.org/A000609 –  Douglas Zare Feb 29 '12 at 22:06

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.

-
Also note that any cut of the copy must preserve come of the original: both pieces in the copy cannot both intersect the sets induced from the original cut. This suggests to me that Aaron has the right order of magnitude in terms of the number of vertices. Gerhard "Ask Me About Cutting Remarks" Paseman, 2012.02.29 –  Gerhard Paseman Feb 29 '12 at 22:34
Why can you pair with $2^d$ cuts from the parallel d-cube? Are these labelled by the vertices of the parallel cube? It seems to me some of them might overlap. –  John Jiang Mar 2 '12 at 19:58
Some unhandwaving: For a given cut of the lower cube, find a hyperplane that achieves it. Wiggle it slightly so that it is not parallel to any line joining two points of that hypercube. After its relationship with the lower cube is established, you can still rotate it so that, as it moves, it intersects exact one point of the upper cube in turn. This gives at least 2^d distinct cuts. Gerhard "Ask Me About System. Design" Paseman, 2012.03.02 –  Gerhard Paseman Mar 2 '12 at 20:49
Further, you will find that the procession of cuts is not arbitrary; each such must at some point duplicate the cut of the lower cube. This restriction leads me to guess that Aaron has the right approximation, but I do not have a proof. Gerhard. "Ask Me About System Design" Paseman, 2012.03.02 –  Gerhard Paseman Mar 2 '12 at 20:53
While I am here, I may as well make the last part explicit. A growth rate polynomial in the number of vertices would imply a bounded multiplicative factor in the (growth of the) number of cuts as the dimension went up by 1. However n/2 is not a bounded multiplicative factor. Gerhard "Ask Me About System Design" Paseman, 2012.03.02 –  Gerhard Paseman Mar 2 '12 at 21:00

An $n$-cube has $\binom{n}{j}2^j$ faces of dimension $n-j$ so the number of cuts is at least $(\sum_0^n\binom{n}{j}2^j)-1-n$. The adjustments are that you seem to want to exclude the $1$ "cut" for $j=0$ which leaves the $n$-cube intact and to only count once each cut into a pair of parallel hyperplanes. If you work out this sum (first without the adjustment terms) I think that you will recognize an exponential growth rate. That gives $3^n-n-1$ which is essential $v^{\log_2{3}}.$ Indeed threshold functions are relevant.

I found claims that the number is of order $\binom{2^n}{n}$ which would be $v^{\log{v}}$, more than polynomial but less than exponential.

-
The growth rate is supposed to be measured against the number of vertices, and not the dimension. I suspect that the growth rate desired by the original poster is subquadratic; perhaps you could check that. Gerhard "Ask Me About Labelling Axes" Paseman, 2012.02.29 –  Gerhard Paseman Feb 29 '12 at 18:08
Sorry, I mean your estimate as measured by the poster is subquadratic. I don't know yet about the actual growth rate. Gerhard "There. Is It Fixed Now?" Paseman, 2012.02.29 –  Gerhard Paseman Feb 29 '12 at 18:11

The sequence you're asking about is more commonly called the number of 'Boolean threshold functions'. It's OEIS A000609, and it starts 2, 4, 14, 104, 1882, 94572, 15028134, 8378070864, 17561539552946, 144130531453121108. It looks like a slowly growing polynomial in the number of vertices. The OEIS page has a bunch of references.

-