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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Académie des sciences
2023-07-01
|
| Series: | Comptes Rendus. Mathématique |
| Online Access: | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.447/ |
| _version_ | 1797651446408151040 |
|---|---|
| author | Jain, Vishesh Pham, Huy Vuong, Thuy-Duong |
| author_facet | Jain, Vishesh Pham, Huy Vuong, Thuy-Duong |
| author_sort | Jain, Vishesh |
| collection | DOAJ |
| description | 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 \gamma ^*(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 $\log \Delta $ 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^{\prime }$ supported in $\mathbb{R}^{O(\log \Delta )}$, such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d^{\prime })$. |
| first_indexed | 2024-03-11T16:15:55Z |
| format | Article |
| id | doaj.art-1b48c082c99f43eab47c474704726d42 |
| institution | Directory Open Access Journal |
| issn | 1778-3569 |
| language | English |
| last_indexed | 2024-03-11T16:15:55Z |
| publishDate | 2023-07-01 |
| publisher | Académie des sciences |
| record_format | Article |
| series | Comptes Rendus. Mathématique |
| spelling | doaj.art-1b48c082c99f43eab47c474704726d422023-10-24T14:19:44ZengAcadémie des sciencesComptes Rendus. Mathématique1778-35692023-07-01361G586987610.5802/crmath.44710.5802/crmath.447Dimension reduction for maximum matchings and the Fastest Mixing Markov ChainJain, Vishesh0Pham, Huy1Vuong, Thuy-Duong2Department of Mathematics, Statistics, and Computer Science, University of Illinois ChicagoDepartment of Mathematics, Stanford UniversityDepartment of Computer Science, Stanford UniversityLet $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 \gamma ^*(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 $\log \Delta $ 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^{\prime }$ supported in $\mathbb{R}^{O(\log \Delta )}$, such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d^{\prime })$.https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.447/ |
| spellingShingle | Jain, Vishesh Pham, Huy Vuong, Thuy-Duong Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain Comptes Rendus. Mathématique |
| title | Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain |
| title_full | Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain |
| title_fullStr | Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain |
| title_full_unstemmed | Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain |
| title_short | Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain |
| title_sort | dimension reduction for maximum matchings and the fastest mixing markov chain |
| url | https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.447/ |
| work_keys_str_mv | AT jainvishesh dimensionreductionformaximummatchingsandthefastestmixingmarkovchain AT phamhuy dimensionreductionformaximummatchingsandthefastestmixingmarkovchain AT vuongthuyduong dimensionreductionformaximummatchingsandthefastestmixingmarkovchain |