Name
Abstract | ||
|---|---|---|
AbstractWe show that the total variation mixing time of the simple random walk on the giant component of supercritical Gn,p and Gn,m is ï log2n. This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are "decorated expanders" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 383-407, 2014 |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/rsa.20539 | Periodicals |
Keywords | Field | DocType |
mixing time,random walk,random graph,expander,giant component | Discrete mathematics,Random regular graph,Combinatorics,Random graph,Exponential function,Expander graph,Vertex (geometry),Simple random sample,Random walk,Giant component,Mathematics | Journal |
Volume | Issue | ISSN |
45 | 3 | 1042-9832 |
Citations | PageRank | References |
18 | 0.90 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Itai Benjamini | 1 | 81 | 14.91 |
| Gady Kozma | 2 | 109 | 6.53 |
| Nicholas C. Wormald | 3 | 1506 | 230.43 |