The birth of the strong components
Time: 10:30 -- Location: à distance
In this talk, I am going to discuss an upcoming paper with Élie de Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina and Stephan Wagner about the asymptotics around the critical window of the phase transition in directed graphs. Although the width of the transition window has been already established in 2009 by Luczak and Seierstad, and some further properties have been obtained very recently in 2019 by other teams, we show how to approach the combinatorics of directed graphs from the viewpoint of pure analytic combinatorics. This systematic framework allows to obtain several new asymptotic results: 1. Directed acyclic graphs. The probability that a random digraph D(n,p) is acyclic is a positive real number when p = C/n, C < 1, which drops to 0 as p = 1/n. We give a precise description of this probability as a function of C and also in the vicinity of p=1/n as a function of the scaling parameter. 2. Precise description of the transition curve. In the model D(n,p), the probability that the strongly connected components of a random digraph are only isolated vertices and loops, drops from 1 to 0, as p is passing the vicinity of 1/n. We obtain an exact expression for this probability rescaled for p around 1/n, as a function of the respective scaling parameter. 3. Complex components. If a component is strongly connected, then a multidigraph obtained by repeatedly removing and smoothing the vertices of in- and out-degree 1 is called its kernel. There are finitely many possible kernels with a given difference between the number of vertices and edges (the latter is called an excess). We show that when p is around 1/n, each cubic kernel (i.e. the kernel whose vertices are of total degrees 3 each) with a given excess appears inside a random digraph with a constant probability, and we also obtain this probability as a function of the scaling parameter. 4. Source-like components. Finally, we can generalise the above tools to obtain the probability that in a random digraph there is a given set of strongly connected components with a given known structure if a given subset of them are source-like.