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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-
Just to make sure, your notion of hyperplane means that the partition has a certain symmetry. In particular, the number of pieces with t points in the piece is always even. Is that what you want? Gerhard "Ask Me About System Design" Paseman, 2012.05.31 – Gerhard Paseman May 31 at 20:52

1
Yeah, that seemed the cleanest way to set it up. Fans of odd numbers are welcome to divide everything by two. – JSE May 31 at 21:13
For those of us with broader interests, can you (edit the post to or give a couple of comments to) provide a brief summary of the original question? (Some of us might want to try a different reformulation.) Gerhard "Acquiring Minds Want To Know" Paseman, 2012.06.01 – Gerhard Paseman Jun 1 at 15:42

1
I'd like to know the connection with evolutionary biology. There is a natural question of how many crossovers it takes to separate genes which are physically close, which might correspond to a nonuniform distribution of hyperplanes which is not symmetric in the coordinates. – Douglas Zare Jun 1 at 17:42
I've added a link to the relevant biology paper in the post. – JSE Jun 1 at 23:16

## 1 Answer

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.

-

2
Each edge intersects a hyperplane iff the partition separates all vertices. Really? I'm not that sure. Take a few planes in $R^3$ parallel to the vector $1,1,0$. You can cross any edge you want with such a hyperplane. However it is quite hard to separate $(1,1,1)$ and $(-1,-1,1)$ by any such plane... – fedja Jun 1 at 1:47
Hmm, good point. – Douglas Zare Jun 1 at 1:53

3
Somewhat annoyingly, it seems like the usual second moment method to get a matching lower bound may not quite work here, or at least not easily. The trouble is that if a hyperplane intersects a given edge, it is significantly more likely to intersect each other edge in the same direction (roughly speaking, if the edges are Hamming distance $d \approx n/2$ apart, hitting the first edge increases the probability the second edge is hit by a factor of $2$). This ends up making the probability that both edges are missed by all $n^{3/2}$ edges much larger than the square of the prob. one is missed – Kevin P. Costello Jun 1 at 21:34
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9413127899169922, "perplexity_flag": "head"}