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

Título
Spectral gap and Mixing time for Random Walks on Expander graphs.
Expositor
Hubert Lacoin

IMPA
Data
Quarta-feira, 10 de outubro de 2018, 15:30
Local
Sala 333
Resumo
(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}$.