*[Note: This question is trivially impossible, though I leave the original form below. If is the uniform measure on , then any two sets of measure are at distance by concentration of measure. Thus it is impossible to find sets satisfying the desired bound. I will try to think of the right question and repost. Unfortunately, I now recall having gone down this path a few times before, and I fear there may not be a relevant elementary open question after all.]*

Here is an interesting and elementary (to state) open question whose resolution would give an optimal higher-order Cheeger esimate. The goal is to replace the factor in Theorem 1 of the previous post with a factor, or even an optimal bound of .

Fix and let denote a probability measure on the -dimensional sphere . For the purpose of this question, one can assume that is supported on a finite number of points. Suppose also that is *isotropic* in the sense that, for every ,

Now our goal is to find, for some , a collection of (measurable) subsets such that for each , and such that for , we have

In Lemma 5 of the previous post, we proved that this is possible for and . In this paper, we improve the estimate on somewhat, though the best-known is still for some .

Question:

Is it possible to achieve ? One could even hope for and .

Two extreme cases are when (1) is uniform on , or (2) is uniform on the standard basis . In the first case, one can easily achieve (in fact, one could even get sets satisfying these bounds). In the second case, taking each set to contain a single basis vector achieves and .

If one only wants to find, say, sets instead of sets, then it is indeed possible to achieve and . *[Update: This is actually impossible for the reasons stated above. To get the corresponding bounds, we do a random projection into dimensions. This only preserves the original Euclidean distances on average.]* Furthermore, for , this bound on is asymptotically the best possible.

How much slack is allowed in the isotropic condition? Suppose $\mu$ is supported on $x_1,\ldots,x_n$ and we don’t have $\sum_i x_ix_i^T = k^{-1}\cdot I$, but we do have, say, $\|\sum_i x_ix_i^T – k^{-1}\cdot I\| \le \gamma$. Is there some value of $\gamma>0$ that is still acceptable for your application?

Comment by minilek — February 23, 2013 @ 5:28 pm

Oh right $\mu$ is part of the input …my above question is probably nonsense.

Comment by minilek — February 23, 2013 @ 5:30 pm

It’s possible that it holds in this greater generality, but even the perfect isotropy case is open.

Comment by James Lee — February 24, 2013 @ 10:42 am