论文标题
最大匹配和最快混合马尔可夫链的尺寸降低
Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain
论文作者
论文摘要
令$ g =（v，e）$是一个无向图，具有最高度$δ$和顶点电导$ψ^*（g）$的图形。我们表明，存在一个对称的随机矩阵$ p $，并在$ e $上支撑了偏高的条目，其光谱间隙差距$γ^*（p）$满足\ [ψ^*（g）^{2}/\logδ\logδ\ logu fimeSimγ^*（p）\ simsim sim sim sim sim insim（p）\ nistim and shim（g），\ m）and shim（g），\] choune和shimψ^*（g）。回答了Olesker-Taylor和Zanetti的问题，他们以$ \logδ$代替了$ \ log | v | $获得了这样的结果。 为了获得我们的结果，我们展示了如何嵌入在$ v $上定义的负类型$ d $ d $中的$ \ m athbb {r}^{r}^{o（\loguΔ）} $支撑的否定性$ d'$，以使得（分数）匹配的（istractional）与权重$（v，v，v，v，e）的匹配数（ $（v，e，d'）$。
Let $G = (V,E)$ be an undirected graph with maximum degree $Δ$ and vertex conductance $Ψ^*(G)$. We show that there exists a symmetric, stochastic matrix $P$, with off-diagonal entries supported on $E$, whose spectral gap $γ^*(P)$ satisfies \[Ψ^*(G)^{2}/\logΔ\lesssim γ^*(P) \lesssim Ψ^*(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Δ$ 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 $\mathbb{R}^{O(\logΔ)}$, such that the (fractional) matching number of the weighted graph $(V,E,d)$ is approximately equal to that of $(V,E,d')$.
