Seminario - Mixing time on dynamic configuration model

Link identifier #identifier__114671-1Link identifier #identifier__73898-2

15 Gennaio 2019, ore 11:30
Dipartimento di Matematica e Fisica, Aula 211
Largo San Leonardo Murialdo, 1 palazzina C - Roma

Martedì 15 gennaio 2019 alle ore 11.30, presso l'Aula 211, il Dipartimento di Matematica e Fisica, ospiterà il seminario del prof. Luca Avena dal 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. 

Per informazioni:
Pietro Caputo
Link identifier #identifier__30882-1caputo@mat.uniroma3.it

Link identifier single category #link-single-category-56072Eventi