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