Integrality gap for Uniform Sparsest Cut

Uniform Sparsest Cut asks for a partition with little capacity crossing the cut relative to the number of vertex pairs it separates. The Goemans–Linial semidefinite relaxation supplies a lower bound. How much larger can the true optimum be?

Why it matters and what counts as progress

Why it matters: The gap limits what this relaxation can guarantee. Near-matching lower and upper bounds show how its accuracy scales with the number of vertices.

What counts as progress: Give explicit or existential instances with a proved ratio between the optimum and a positive relaxation value, or improve the universal upper bound. Keep the uniform-demand assumption explicit.

How the problem developed

  1. 2009 · Square-root logarithmic upper bound [1]

    Sanjeev Arora, Satish Rao and Umesh Vazirani Obtained an approximation and matching-order upper bound on the semidefinite gap of order (log⁡n)\sqrt{(\log n)}.

  2. 6 Oct 2026 · Reported near-matching integrality gap [2]

    OpenAI’s internal model For a sequence of n-vertex uniform-demand instances, the Goemans–Linial SDP integrality gap is at least c(log⁡n)/(log⁡log⁡n)3c\sqrt{(\log n)}/(\log \log n)^{3} for an absolute c>0c>0.

AI contribution

Sources

  1. Expander flows, geometric embeddings and graph partitioning
  2. Near-square-root logarithmic integrality gaps for uniform sparsest cut
  3. OpenAI mathematics release
  4. OpenAI’s Lean scope for this manuscript
Publication history