论文标题
Cayley图的混合时间的敏感性
Sensitivity of mixing times of Cayley graphs
论文作者
论文摘要
我们表明，即使对于Cayley图，总的变化混合时间也不是准偶然的。也就是说，我们构建了一对序列的Cayley图，它们之间的地图以有界的方式扭曲度量，而两个混合时间的比率则是无穷大。用作示例的Cayley图具有无界度。 对于非交易图，我们构建了有界度图，为一个图的混合时间渐近地比混合时间小于从1+o（1）$增加一些边缘重量从1+$ 1+o（1）$增加的网络上随机步行的最佳起点。
We show that the total variation mixing time is not quasi-isometry invariant, even for Cayley graphs. Namely, we construct a sequence of pairs of Cayley graphs with maps between them that twist the metric in a bounded way, while the ratio of the two mixing times goes to infinity. The Cayley graphs serving as an example have unbounded degrees. For non-transitive graphs we construct bounded degree graphs for which the mixing time from the worst starting point for one graph is asymptotically smaller than the mixing time from the best starting point of the random walk on a network obtained by increasing some of the edge weights from 1 to $1+o(1)$.
