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\frac 2 \pi + o_{n,d}(1)\right)/\sqrt d, where 2\frac 2 \pi = 1.595\ldots 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\rightarrow \infty and then the limit d \rightarrow \infty. This is established by analyzing linear-size cuts using techniques of Jagannath and Sen \mbox{%DIFAUXCMD jagannath2017unbalanced 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))/\sqrt d, which is met by d-regular Ramanujan graphs, generalizing a lower bound of Srivastava and Trevisan \mbox{%DIFAUXCMD ST18 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\ldots + o_{n,d}(1))/\sqrt d, while every (weighted subgraph) spectral sparsifier of G having average degree d has approximation error at least (2-o_{n,d}(1))/\sqrt d.
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\frac 2 \pi + o_{n,d}(1)\right)/\sqrt d, where 2\frac 2 \pi = 1.595\ldots 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\rightarrow \infty and then the limit d \rightarrow \infty. This is established by analyzing linear-size cuts using techniques of Jagannath-Sen '17 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))/\sqrt d, which is met by d-regular Ramanujan graphs, generalizing a lower bound of Srivastava-Trevisan '18. 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\ldots + o_{n,d}(1))/\sqrt d, while every (weighted subgraph) spectral sparsifier of G having average degree d has approximation error at least (2-o_{n,d}(1))/\sqrt d.
R
Jagannath and Sen \mbox{%DIFAUXCMD jagannath2017unbalanced
Jagannath-Sen '17
R
Srivastava and Trevisan \mbox{%DIFAUXCMD ST18
Srivastava-Trevisan '18.