In celebration of the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava, here is a question on isotropic point sets on which Kadison-Singer does not (seem to) shed any light. A positive resolution would likely have strong implications for the Sparsest Cut problem and SDP hierarchies. The question arose in discussions with Shayan Oveis Gharan, Prasad Raghavendra, and David Steurer.
Open Question: Do there exist constants such that for any , the following holds? Let be a collection of orthonormal bases and define . Then there are subsets with and .
[Some additional notes: One piece of intuition for why the question should have a positive resolution is that these orthonormal bases which together comprise at most vectors cannot possibly “fill” -dimensional space in a way that achieves -dimensional isoperimetry. One would seem to need points for this.
One can state an equivalent question in terms of vertex expansion. Say that a graph on vertices is a vertex expander if for all subsets with . Here, denotes all the nodes that are in or are adjacent to . Then one can ask whether there exists a 1-1 mapping from to for some orthonormal bases such that the endpoints of every edge are mapped at most apart (as ).]