Loading...
Please wait, while we are loading the content...
Similar Documents
Cutoff for random lifts of weighted graphs
| Content Provider | Semantic Scholar |
|---|---|
| Copyright Year | 2019 |
| Abstract | We prove a cutoff for the random walk on random $n$-lifts of finite weighted graphs, even when the random walk on the base graph $\mathcal{G}$ of the lift is not reversible. The mixing time is w.h.p. $t_{mix}=h^{-1}\log n$, where $h$ is a constant associated to $\mathcal{G}$, namely the entropy of its universal cover. Moreover, this mixing time is the smallest possible among all $n$-lifts of $\mathcal{G}$. In the particular case where the base graph is a vertex with $d/2$ loops, $d$ even, we obtain a cutoff for a $d$-regular random graph (as did Lubetzky and Sly in \cite{cutoffregular} with a slightly different distribution on $d$-regular graphs, but the mixing time is the same). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/1908.02898v1.pdf |
| Alternate Webpage(s) | http://export.arxiv.org/pdf/1908.02898 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
