Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Abstract

Let $G=(V,E)$ be an undirected graph with maximum degree $\Delta$ and vertex conductance ${\Psi }^{\ast }(G)$. We show that there exists a symmetric, stochastic matrix $P$, with off-diagonal entries supported on $E$, whose spectral gap ${\gamma }^{\ast }(P)$ satisfies \[Ψ^*(G)^{2}/\logΔ\lesssim γ^*(P) \lesssim Ψ^*(G).\] Our bound is optimal under the Small Set Expansion Hypothesis, and answers a question of Olesker-Taylor and Zanetti, who obtained such a result with $\log \Delta$ replaced by $\log |V|$. In order to obtain our result, we show how to embed a negative-type semi-metric $d$ defined on $V$ into a negative-type semi-metric $d^{\prime }$ supported in ${\mathbb{R}}^{O(\log \Delta )}$, such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d^{\prime })$.

6 pages