Portal de Periódicos da CAPES

On sensitivity of uniform mixing times

2018; Institute of Mathematical Statistics; Volume: 54; Issue: 1 Linguagem: Francês

10.1214/16-aihp802

1778-7017

Jonathan Hermon,

Random Matrices and Applications

Nous montrons que le temps de mélange pour la distance $L_{\infty}$ d'une marche aléatoire sur une suite de graphe de taille $n$ et de degré uniformément borné peut être multiplié par un facteur d'ordre $\log\log n$ (optimal) en perturbant le poids des arrêtes du graphe de manière uniformément bornée. Ceci résout une question et une conjecture de Kozma.