Long-Range Percolation Mixing Time

Source abstract

We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotic almost sure mixing time of the graph created by long-range percolation on the cycle of length N ( $\Integer/N\Integer$ ). While it is known that the asymptotic almost sure diameter drops from linear to poly-logarithmic as the exponent s decreases below 2 [4, 9], the asymptotic almost sure mixing time drops from N 2 only to N s -1 (up to poly-logarithmic factors).