Extremal stationary values for random digraphs

Add to your list(s) Download to your calendar using vCal

• Guillem Perarnau (Polytechnic University of Catalonia)
• Thursday 19 November 2020, 16:00-17:00
• https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09.

If you have a question about this talk, please contact M.Jenssen.

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 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” trajectories, controlled by large deviation rate functions. As a by-product of our proof, we also determine the hitting and cover time in random digraphs. This is joint work with Xing Shi Cai. __

Meeting ID: 830 2268 5017 Passcode: 101833

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• https://bham-ac-uk.zoom.us/j/83022685017?pwd=L1RQclI2dmIvL2RXeUNCblpuanlBUT09

Note that ex-directory lists are not shown.