The evolution of the mixing rate of a simple random walk on the giant component of a random graph
The evolution of the mixing rate of a simple random walk on the giant component of a random graph
复制标题
随机图巨大分量上简单随机游走混合率的演化
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
B. Reed
中科院分区：
文献类型：
--
作者：
N. Fountoulakis;B. Reed
在这篇文章中，我们提出了一个超临界随机图的最大组件，也被称为巨组件上的随机游动的混合时间的研究。当平均度d最多为O（$ \sqrt{\ln n} $）时，我们确定了减慢随机游走的局部障碍物，证明了在这种情况下混合时间几乎必然渐近地为Θ（（n/d）2）.随着平均度的增长，这些变得可以忽略不计，并且是最大组分的直径接管，产生混合时间Θ（n/d）a.a.s.。我们在2003-04学年证明了这些结果。类似的结果，但常数d后来证明了Benjamini等人。© 2008 Wiley Periodicals，Inc.随机结构算法，2008
In this article we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most O($ \sqrt{\ln n} $), proving that the mixing time in this case is Θ((n/d)2) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time Θ(n/d) a.a.s.. We proved these results during the 2003–04 academic year. Similar results but for constant d were later proved independently by Benjamini et al. in 3 . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008