论文标题
在常规图上混合边缘翻转时间边界
Mixing time bounds for edge flipping on regular graphs
论文作者
论文摘要
边缘翻转是给定连接图上的非可逆Markov链，该图由Chung和Graham定义。在同一篇论文中，确定了某些图形的特征值和固定分布。我们进一步研究其光谱特性，以显示常规图的收敛速率的下限。此外，我们表明，通过耦合参数在完整图上的边缘翻转的边缘在1/4 n 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 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 1/4 n log n for the edge flipping on the complete graph by a coupling argument
