Critical random graphs: Diameter and mixing time (Q941296): Difference between revisions

The mixing time of a random walk on a graph is defined as the waiting time \(t\) for closeness between the t-step transition probabilities and the stationary probabilities. For a random graph \(G(n,p)\), its largest connected component \(C\) and the mixing time of a random walk on \(C\) are investigated. The diameter of \(C\) and the mixing time are specified for \(p\) in the vicinity of \(1/n\). Generalizations to graphs with bounded degrees are also considered.