Critical random graphs: Diameter and mixing time (Q941296)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5321181
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Critical random graphs: Diameter and mixing time |
scientific article; zbMATH DE number 5321181 |
Statements
Critical random graphs: Diameter and mixing time (English)
0 references
4 September 2008
0 references
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.
0 references
Random graph
0 references
Random walk
0 references
Mixing time
0 references
Connected component
0 references
Percolation
0 references
0 references
0.8587688207626343
0 references
0.841749906539917
0 references
0.8211521506309509
0 references
0.8018225431442261
0 references
0.8013831973075867
0 references
