Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

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