Combinatoire, Probabilités

Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain

Jain, Vishesh¹  ; Pham, Huy² ; Vuong, Thuy-Duong³

¹ Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago
² Department of Mathematics, Stanford University
³ Department of Computer Science, Stanford University

Comptes Rendus. Mathématique, Tome 361 (2023) no. G5, pp. 869-876

Résumé

Let $G=(V,E)$ be an undirected graph with maximum degree $\Delta$ and vertex conductance ${\Psi }^{*}\left(G\right)$. We show that there exists a symmetric, stochastic matrix $P$, with off-diagonal entries supported on $E$, whose spectral gap ${\gamma }^{*}\left(P\right)$ satisfies

$${\Psi }^{*}{\left(G\right)}^2/log\Delta \lesssim {\gamma }^{*}\left(P\right)\lesssim {\Psi }^{*}\left(G\right).$$

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\left|V\right|$.

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 ${ℝ}^{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 })$.

Détail

Reçu le : 2022-03-09
Révisé le : 2022-07-21
Accepté le : 2022-11-22
Publié le : 2023-07-18

DOI : 10.5802/crmath.447

Licence : CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits