Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification

Antares Chen, Jonathan Shi, Luca Trevisan

We prove that a random $d$-regular graph, with high probability, is a cut sparsifier of the clique with approximation error at most $\left(2\sqrt{\frac 2 π} + o_{n,d}(1)\right)/\sq…