most recent 30 from http://mathoverflow.net 2013-06-18T22:13:45Z http://mathoverflow.net/feeds/question/89875 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89875/number-of-hyper-cube-cuts Robert 2012-02-29T16:11:32Z 2012-03-02T19:31:25Z

<p>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. </p> <p>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.</p>

http://mathoverflow.net/questions/89875/number-of-hyper-cube-cuts/89885#89885 Aaron Meyerowitz 2012-02-29T17:32:47Z 2012-02-29T18:42:10Z

<p>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. <strike>If you work out this sum (first without the adjustment terms) I think that you will recognize an exponential growth rate. </strike> That gives $3^n-n-1$ which is essential $v^{\log_2{3}}.$ Indeed threshold functions are relevant. </p> <p>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.</p>

http://mathoverflow.net/questions/89875/number-of-hyper-cube-cuts/89896#89896 Gerhard Paseman 2012-02-29T19:18:41Z 2012-02-29T19:18:41Z

<p>Here is some handwaving which suggests that the growth rate is faster than polynomial.</p> <p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.02.29</p>

http://mathoverflow.net/questions/89875/number-of-hyper-cube-cuts/90066#90066 Carl Feynman 2012-03-02T19:31:25Z 2012-03-02T19:31:25Z

<p>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.</p>