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?
Table of contents
Limiting probabilities for digraph families
In our preprint "The birth of the strong components", we are looking at random digraphs which have vertices and whose edges are drawn independently with probability for all of the possible edges.
When , 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
We have also obtained a more refined description:
The figure on the right is obtained by zooming inside the centre of the phase transition. The "correct" zooming factor around this point is , and the resulting probability is proportional to (these two facts are a priori independent).
The three curves corresponding to simple digraphs (), strict simple digraphs () and multidigraphs () 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
and when we move around the critical point, we obtain
Variations on acyclicity
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.
Definition. If a digraph only contains strongly connected components of this type, we call it an elementary digraph.
The probability that a digraph is elementary, drops from 1 to 0 as the scaling parameter goes from to .
Mysteriously, this probability, as a function of , is again expressed as a complex integral involving the derivative of the Airy function:
We get variations on Airy integrals again and again whenever we require any specific structure of strongly connected components, which may go well beyond elementary digraphs: digraphs with a bicyclic component, or with a fixed number of components of given excesses, etc.
Knessl's paper
Here is a bibliographic entry of the paper that I found by a sheer luck. This paper is not easily available online (unless you know how to use sci-hub, or if your university subscription allows you to access it), so I just attach the pdf file of it directly.
Perhaps I may have messed up with terminology, and what I called the "parabolic drift" might turn to be linear drift according to the classical definition. I don't know the formal definition of drift anyway!
Here is a screenshot from Knessl's paper:
and he provides an analytic solution to this problem which is the Airy integral:
Remarkably, when , we obtain the rescaled asymptotic probability of directed acyclic graphs times , so in fact, .
Brownian excursions and critical random graphs
This work is published in the Annals of Probability.
I have thought for a long time that we have a unique way of discovering Airy functions and complex integrals because we were so smart with using Cauchy theorem and generating functions. But Aldous have invented a different approach to arrive to the same mathematical objects in the limit, by using stochastic processes.
In the critical phase of the phase transition of graphs, the complex connected components have sizes and there is a discrete random number of them (remember the Bratelli diagram we discussed with bicyclies, tricycles and so on?). Aldous managed to provide a scaling limit to the whole array of the sizes of these components (rescaled by ) and interpret it in terms of Brownian motion.
Here is a combinatorial interpretation for subtracting the minimum. When we finish exploring a connected component, the height of the excursion is the same as in the beginning of an exploration. Then, by construction, we take one step down when we start exploring the next component. This step down may relate to trees which typically have a very small size, but may also refer to complex components which are larger. There are many trees, though, so we can have several negative steps in a row.
I am not sure I provided this intuition correctly, but the idea is that you split the excursions into several chunks, and each chunk will correspond to a complex connected component.
The surplus edges that appear on the way can serve as decorations inside the parts corresponding to excursions. Finite excess (surplus edges) corresponds then to a finite number of Christmas toys. They are not shown no the above picture, but I am sure that there are papers that comment on these decorations.
The existence of the limit has been conjectured or speculated for a while and Aldous presented the explicit form for this limit using (whatever it means).
Goldschmidt and Stephenson paper
Here is the last paper that provides a beautiful link between Brownian motions and strong components of digraphs.
Christina kindly explained some of its ideas to me and Élie de Panafieu during the ALEA meeting in 2019.
In the paper, they show that the strongly connected components in a critical digraph rescaled by
converge in distribution to a sequence of finite strongly connected multidigraphs. Note that they are dealing directly with convergence of digraphs in some topological / probability space, and not just with the sizes of the components.
Conclusion
I see no trace of the Airy integral formula in the paper of Goldschmidt and Stephenson, but maybe it is already implicitly there?
It would be nice to have a "simple" explanation which links the Airy integrals, digraphs and Brownian motions that does not have to resort to a sophisticated generating function argument.