SEMINARIO

Luca Avena (Leiden University, NL)

Martedi' 15 Gennaio 2019 ORE 11:30

Dipartimento di Matematica e Fisica Universita' degli Studi Roma Tre Largo San Leonardo Murialdo,1 - Pal.C - Aula 211

Titolo: Mixing time on dynamic configuration model

Abstract: We are interested in understanding the mixing time (i.e. the time to reach equilibrium) for a discrete-time random walk moving on a network changing over time in a random fashion. To this aim, we consider a specific model where the underlying evolving network has n vertices, it is initially sampled from the so-called configuration model (a random graph ensemble with a prescribed vertex-degree sequence) and at each time-unit a given fraction of the edge set is randomly rewired. We characterize the mentioned mixing-time for a random walk without backtracking as a function of the fraction of rewired edges. This work extends to a dynamic setup previous works on random walks on static random graphs. In particular, we show that the mixing-time is speeded-up by the presence of the edge-rewiring dynamics and depending on whether such a dynamics is slow, moderate or fast, we show the presence of so-called cutoff , half-cutoff, or absence of cutoff, respectively. Joint work with Hakan Guldas, Remco van der Hofstad and Frank den Hollander