Partitioning the vertices of an n-cube with random hyperplane cuts

2012-05-31T20:11:31Z

An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.

It is an old chestnut of a problem to ask: into how many pieces can an n-sphere be cut by k hyperplanes? (Here I want the hyperplanes to be honest linear subspaces, not affine ones as in the classical "lazy caterer" problem, but the flavor is much the same.)

Now suppose that instead of the sphere, I have the 2^n vertices of the n-cube, i.e. the set {-1,1}^n. I cut this set with k random hyperplanes. Now I have a partition of 2^n.

What do I expect this partition to look like? E.G. how many blocks are there? How big is the largest blocks? Are the biggest blocks "close to each other" in the sense that you can pass from one to the other without crossing very many of the hyperplanes? (To formalize this, one might say that the structure one is studying isn't just a partition, but a partition in which each block is identified with an element of (Z/2Z)^k, thus providing a notion of Hamming distance between block.)

I have asked this question in a rather vague way by not specifying what range of k relative to n is in play. This should actually be considered part of the question: what are the threshold curves in the (n,k) plane, if any, where the partition sharply changes its expected nature? My biologist friend is certainly interested mostly in the case k > n; I think he's most interested in the case where k is bounded between n and a constant multiple of n, but I'm not sure. I expect he would be interested to know, for instance, how big k needs to be before all blocks of the partition are singletons almost surely.

Further remarks: though I don't think this is relevant to MBF, one could certainly pass from a discrete to a continuous setting and ask about the statistics of the partition of the volume of the unit (n-1)-sphere by the k hyperplane cuts, which would also be interesting. Or, instead of letting the cuts be chosen randomly from a continuous distribution, you could let them be chosen from the vertices of a cube in the dual R^n; in other words, you could choose at random from hyperplanes of the form x_1 +- x_2 +- ... +-x_n. This last version is probably closest to what MBF is actually thinking about.

Update: A couple of people asked about the biological context. Here's the original paper.

http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fjournal.pcbi.1000202

Answer by Douglas Zare for Partitioning the vertices of an n-cube with random hyperplane cuts

2012-05-31T23:51:17Z

I corrected an earlier version which assumed that only adjacent vertices need to be separated to guarantee the parts are singletons, which fedja pointed out was incorrect. Thanks.

Here is a partial answer to the question of how many cuts it takes before the nonempty pieces are singletons with high probability when the hyperplanes are chosen uniformly. Consider the roughly $4^n$ pairs of vertices of the cube. Each pair is separated by a hyperplane iff the partition separates all vertices. The expected number of pairs which intersect no hyperplane is at most $4^n$ times the probability that a particular edge is missed, since adjacent vertices are the least likely to be separated. The probability that none of the $k$ hyperplanes intersects an edge is $p^k$, where $p$ is the probability that each hyperplane misses the edge.

What does it take for a hyperplane to separate two adjacent vertices? These points determine a great circle, and are at angle $\arccos \frac{n-2}{n} \approx \frac{2}{\sqrt n}$. The hyperplane almost surely intersects this circle in two antipodal points. If these intersect the arc of about $\frac{2}{\sqrt n}$ radians, then the hyperplane intersects the edge. So, the probability that a random hyperplane intersects an edge is about $\frac{2}{\pi\sqrt n}$. The probability the edge is missed is the complement, about $1- \frac{2}{\pi\sqrt n}$. The probability all $k$ hyperplanes miss this edge is about $(1- \frac{2}{\pi\sqrt n})^k \approx \exp(-\frac{2k}{\pi\sqrt n})$. The expected number of pairs not separated by any hyperplane is at most about $4^n \exp(-\frac{2k}{\pi\sqrt n})$.

If you choose $k\approx c n^{3/2}$ then the expected number of pairs not separated by any hyperplane is at most $1$. For much larger $k$ the expected number of pairs of vertices in the same part, hence the probability that two vertices are in the same part, becomes small.

Partitioning the vertices of an n-cube with random hyperplane cuts - MathOverflow

Partitioning the vertices of an n-cube with random hyperplane cuts

Answer by Douglas Zare for Partitioning the vertices of an n-cube with random hyperplane cuts