# non-separable assignments of the vertices of a hypercube

I have a question regarding exercise 14.17 in An Introduction to Information Retrieval by Manning et al.

The problem is:

"Assuming two classes, show that the percentage of non-separable assignments of the vertices of a hypercube decreases with dimensionality M for M > 1. For example, for M = 1 the proportion of non-separable assignments is 0, for M = 2, it is 2/16. Solve the exercise either analytically or by simulation."

The total number of assignments of vertices of an N-dimensional hypercube is: $$2^{(2^N)}$$

And as I found in here the number of separable assignments is O($$2^{(N^2)}$$). So the percentage of non-separable assignments is increasing with N (which is the opposite of what is said in the exercise).

What am I missing here?

• I agree, this seems incorrect. – Ben Reiniger Jun 19 '19 at 21:36

Let $$s(n)$$ denote the number of separable sets in the $$n$$-cube. Let $$Q_0, Q_1$$ denote the subcubes of one smaller dimension, with say last coordinates equal to 0, 1 respectively. The key fact is that any separable set of the whole cube intersects with each of $$Q_0, Q_1$$ in separable sets. (The separating hyperplane intersects the codimension-1 spaces to form separating hyperplanes.) So $$s(n)\leq [s(n-1)]^2.$$
Now the proportion $$r(n)$$ satisfies $$r(n)= \frac{s(n)}{2^{2^n}}\leq \frac{[s(n-1)]^2}{(2^{2^{n-1}})^2}= [r(n-1)]^2< r(n-1),$$ where the last inequality holds because $$r(n-1)<1$$ for $$n>2$$.