Is there anything known about the mixing time of a simple random walk on an Erdos-Renyi graph with parameter $\langle n,d \rangle$ where $d=n^a (0<a<1 )$. I know about Reed et al and Benjamini et al's result when $d=\log^a (n)$. But I need to have a denser random graph.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Here d is the average degree? If so, it is probably ~log(n). If you wish, I can later search for a source. $\endgroup$– BachCommented Mar 29, 2017 at 6:11
-
$\begingroup$ Yes, I mean the average degree. Yeah that would be awesome, do you know of any source? $\endgroup$– shahrzad haddadanCommented Mar 29, 2017 at 8:42
-
$\begingroup$ I believe I found it. It is a paper by Hildebrand. Thanks. $\endgroup$– shahrzad haddadanCommented Mar 29, 2017 at 14:13
Add a comment
|