论文标题
在常规图上混合边缘翻转时间边界
Mixing time bounds for edge flipping on regular graphs
论文作者
论文摘要
边缘翻转是给定连接图上的非可逆马尔可夫链，该图由Chung和Graham在[CG12]中定义。在同一篇论文中，确定了某些图形的特征值和固定分布。我们进一步研究其光谱特性，以显示常规图的收敛速率的下限。此外，我们表明，通过耦合参数在完整的图上翻转边缘的边缘\ frac {1} {1} {4} {4} {4} n \ log n发生截止。
The edge flipping is a non-reversible Markov chain on a given connected graph, which is defined by Chung and Graham in [CG12]. In the same paper, its eigenvalues and stationary distributions for some classes of graphs are identified. We further study its spectral properties to show a lower bound for the rate of convergence in the case of regular graphs. Moreover, we show that a cutoff occurs at \frac{1}{4} n \log n for the edge flipping on the complete graph by a coupling argument.
