<aside> 👀 When we look at the probabilities of appearance of different digraph families inside the window of the phase transition, we obtain certain integrals of Airy functions in the complex plane. Similar integrals arise in the study of Brownian motion with drift. Furthermore, the latter has already been given interpretation for graphs and digraphs in earlier papers. But the complete picture is elusive because I don't have sufficient background.
Is it possible to provide a "simple" explanation to the formulas that we observe?
</aside>
Table of contents
In our preprint "The birth of the strong components", we are looking at random digraphs $D(n,p)$ which have $n$ vertices and whose edges are drawn independently with probability $p$ for all of the $n(n-1)$ possible edges.
Example: digraph with 3 vertices and 3*2 = 6 directed edges.
<aside> 🤔
When $p = 1/n$, the digraph undergoes a phase transition. There are several events happening around this point. For example, if we want to provide a rough description for acyclicity, we could say that when $p = \lambda / n$,
$$ \mathbb P(\text{digraph is acyclic}) \to \begin{cases} e^{\lambda}(1-\lambda), & \lambda < 1,\\ 0, & \lambda \geqslant 1 \end{cases} $$
</aside>
We have also obtained a more refined description:
It is also possible to consider strict digraph families $\mathbb{SD}$ where 2-cycles are forbidden, or multidigraphs $\mathbb{MD}$ where multiplicities and loops are allowed.
The figure on the right is obtained by zooming inside the centre of the phase transition. The "correct" zooming factor around this point is $n^{1/3}$, and the resulting probability is proportional to $n^{-1/3}$ (these two facts are a priori independent).
The three curves corresponding to simple digraphs ($\mathbb{D}$), strict simple digraphs ($\mathbb{SD}$) and multidigraphs ($\mathbb{MD}$) are obtained from one another by multiplying by a rescaling factor, and I personally prefer the one with multidigraphs because it has the simplest possible form.
So, in particular, for multidigraphs
$$ \mathbb P_{\mathsf{acyclic}}(n, 1/n) \to \gamma_1 n^{-1/3}, \quad \gamma_1 = \dfrac{2^{-1/3}}{2 \pi i} \int_{-i \infty}^{i \infty} \dfrac{1}{\operatorname{Ai}(-2^{1/3} t)} dt \approx 0.488736706 $$
and when we move around the critical point, we obtain
We can express limiting probabilities of other events using Airy integrals. One signature of the phase transition is that the probability of a certain event drops from 1 to 0. Let us look at the probability that all the strongly connected components are either single vertices or cycles.
Allowed strongly connected components.