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 $\gamma ^*(P)$ satisfies \[ \Psi ^*(G)^{2}/\log \Delta \lesssim \gamm...
| Główni autorzy: | , , |
|---|---|
| Format: | Artykuł |
| Język: | English |
| Wydane: |
Académie des sciences
2023-07-01
|
| Seria: | Comptes Rendus. Mathématique |
| Dostęp online: | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.447/ |