Para receber por e-mail novas publicações de Seminário de Probabilidade e Combinatória, Clique Aqui!

Seminários do IMPA

Probabilidade e Combinatória

Spectral gap and Mixing time for Random Walks on Expander graphs.
Hubert Lacoin

Quarta-feira, 10 de outubro de 2018, 15:30
Sala 333
(joint with Charles Bordenave (Marseille))
It is a classic fact of probability the marginal distribution a reversible random walk on a connected finite graph converges to the equilibrium measure. The time needed to come close to this equilibrium, known as the Mixing Time, is very much related with the spectral properties of the transition matrix associated with the walk. A striking result illustrating this link, recently proved by Peres and Lubetzky states that if the largest non-trivial eigenvalue for the adjacency matrix of a $d$ regular graph on $N$ vertices is close to its minimal possible value $2\sqrt{d-1}$, then the mixing time also has to be minimal and is of order $\frac{d}{d-2}\frac{\log N}{\log d-1}$.