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

We prove that a random d-regular graph, with high probability, is a cut sparsifier of the clique with approximation error at most 2 2 π + o n,d (1) / √ d, where 2 2 π = 1.595 . . . and o n,d (1) denotes an error term that depends on n and d and goes to zero if we first take the limit n → ∞ and then the limit d → ∞. This is established by analyzing linear-size cuts using techniques of Jagannath and Sen [13] derived from ideas in statistical physics, and analyzing small cuts via martingale inequalities.

We also prove new lower bounds on spectral sparsification of the clique. If G is a spectral sparsifier of the clique and G has average degree d, we prove that the approximation error is at least the "Ramanujan bound" (2 -o n,d (1))/ √ d, which is met by d-regular Ramanujan graphs, provided that either the weighted adjacency matrix of G is a (multiple of) a doubly stochastic matrix, or that G satisfies a certain high "odd pseudo-girth" property. The first case can be seen as an "Alon-Boppana theorem for symmetric doubly stochastic matrices," showing that a symmetric doubly stochastic matrix with dn non-zero entries has a non-trivial eigenvalue of magnitude at least (2 -o n,d (1))/ √ d; the second case generalizes a lower bound of Srivastava and Trevisan [23], which requires a large girth assumption.

Together, these results imply a separation between spectral sparsification and cut sparsification. If G is a random log n-regular graph on n vertices (this is to ensure that G, and consequently any d-regular subgraph, has high pseudogirth), we show that, with high probability, G admits a (weighted subgraph) cut sparsifier of average degree d and approximation error at most (1.595 . . . + o n,d (1))/ √ d, while every (weighted subgraph) spectral sparsifier of G having average degree d has approximation error at least (2 -o n,d (1))/ √ d.