# Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

arXiv: https://arxiv.org/abs/2203.03858 · HTML: https://mlsanity.com/paper/2203.03858/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2022.

## Built on by (most cited first, 1 of 1)

- [Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues](https://mlsanity.com/paper/2211.09776/) (2022)

## Abstract (arXiv)

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').