Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
This doesn't answer the question, but has some references and another term: oeis.org/A000609 –  Douglas Zare Feb 29 '12 at 22:06
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.