[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 .
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.