Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Let G = (V,E) be an undirected graph with maximum degree Delta and vertex conductance Psi^*(G). We show that there exists a symmetric, stochastic matrix P, with off-diagonal entries supported on E, whose spectral gap γ^*(P) satisfies [Psi^*(G)2/logDelta lesssim γ^*(P) lesssim Psi^*(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 logDelta 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' supported in ℝO(logDelta), such that the (fractional) matching number of the weighted graph (V,E,d) is approximately equal to that of (V,E,d').