The balanced separator conjecture for sphere intersection graphs

Let t,dgreaterthanorequalto1t,d greater than or equal to 1 be integers, and let GG be an nn-vertex graph in the class \SphereIntdt\SphereInt{d}_t of sphere intersection graphs. A balanced separator is a vertex set whose removal leaves no connected component with more than a fixed balanced fraction of the vertices. Balanced separator conjecture. Every such graph has a balanced separator of size

\bigOt,d(n11d+1).{\bigO{}}_{t,d}(n^{1-\frac{1}{d+1}}).

The conjecture would improve the exponent in the known separator theorem for sphere intersection graphs. It is known for d=1d=1, while the general case remains open.

Sources & referencesView supporting material

Primary source

James Davies, Agelos Georgakopoulos, Meike Hatzel and Rose McCarty, “Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs”, arXiv:2504.00932 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.