Extremal stationary values for directed random graphs

Abstract: : In this talk, we will discuss the minimum positive value of the stationary distribution of a random walk on a directed random graph with given (bounded) degrees. While for undirected graphs the stationary distribution is simply determined by the degrees, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determining the mixing time of the walk, as shown by Bordenave, Caputo, and Salez. However, typical results provide no information on the minimum value, which is important for many applications. Recently, Caputo and Quattropani showed that the stationary distribution exhibits logarithmic fluctuations provided that the minimum degree is at least 2. In this talk, we show that dropping the minimum degree condition may yield polynomially smaller stationary values of the form $n^{-(1+C+o(1))}$, for a constant C determined by the degree distribution. In particular, C is the combination of two factors: (1) the contribution of atypically thin in-neighborhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" directed paths, controlled by large deviation rate functions. As a by-product of our proof, we also determine the mean hitting time in random digraphs. This is joint work with Xing Shi Cai.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).