Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong

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 entr…