Seminari del Dipartimento
Fisica Matematica Exploration processes of critical random structures G. Bet 24-04-2018 - 14:30 Largo San Leonardo Murialdo,1 - Pal.C - AULA 311
The study of random graphs (RGs) from a probabilistic point of view has grown rapidly in the last decade. On one hand, RG models can account for much of the complexity of modern-day networks (telecommunication networks, etc) while still being amenable to exact mathematical analysis. On the other hand, RGs are an excellent toy model for the phase transition behaviour of more complicated structures. The most famous example is perhaps the Erdos-Renyi RG (ERRG), where each of n vertices is connected to any other vertex with equal probability p<1. A celebrated result by Aldous shows that the ERRG undergoes a phase transition when np = 1 + c*n^{-1/3}, for a constant c (the so-called critical regime). He proved this by introducing a certain process which explores and generates the RG at the same time. This profound insight leads to a powerful set of tools (borrowed from the theory of stochastic processes) which can shed light on the critical behaviour of RGs models. I will discuss how the exploration process of Aldous lends itself, perhaps surprisingly, to a queueing-theoretical interpretation and how this leads to a precise description of the critical behaviour of a large class of inhomogeneous random graphs (and of the associated queueing models). |