Cut Sparsification of the Clique Beyond the Ramanujan Bound
share
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 <cit.> derived from ideas from statistical physics and analyzing small cuts via martingale inequalities. We also prove that every spectral sparsifier of the clique having average degree d and a certain high "pseudo-girth" property has an approximation error that is at least the "Ramanujan bound" (2-o_n,d(1))/√(d), which is met by d-regular Ramanujan graphs, generalizing a lower bound of Srivastava and Trevisan <cit.>. Together, these results imply a separation between spectral sparsification and cut sparsification. If G is a random log n-regular graph on n vertices, 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).
READ FULL TEXT