4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Joseph O'Rourke
    Commented Feb 29, 2012 at 16:55
  • $\begingroup$ Oh, I see from Gerhard's comment that I misread: I meant the number grows exponentially with the dimension $d$. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 29, 2012 at 18:36
  • $\begingroup$ It may be of order $2^{n^2}$ which would be $v^{\log{v}}$ $\endgroup$
    – Aaron Meyerowitz
    Commented Feb 29, 2012 at 18:43
  • 1
    $\begingroup$ This doesn't answer the question, but has some references and another term: oeis.org/A000609 $\endgroup$
    – Douglas Zare
    Commented Feb 29, 2012 at 22:06

3 Answers 3

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 29, 2012 at 22:34
  • $\begingroup$ 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. $\endgroup$
    – John Jiang
    Commented Mar 2, 2012 at 19:58
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 2, 2012 at 20:49
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 2, 2012 at 20:53
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Mar 2, 2012 at 21:00
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 29, 2012 at 18:08
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 29, 2012 at 18:11
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .