The structure of large random graphs

Thesis

We obtain universality results on the structure of random graphs from two different angles. Naturally, there is a trade-off between the generality of the assumptions on a model and the specificity of the results one may obtain. The strength of the first work is its generality: we obtain non-asymptotic universal tail bounds on the height of random trees that do not require any assumptions on e.g. the tail behaviour of the degrees. In the second work, we need stronger assumptions, but our description of the structure is more specific: we do not study a real-valued statistic of the random graph model, but show convergence in distribution under rescaling of the graph itself, which entails the convergence of a whole panoply of such statistics.

Firstly, we obtain new non-asymptotic universal tail bounds for the height of uniformly random trees with a given degree sequence. We also obtain universal tail bounds for the height of simply generated trees and conditioned Bienaymé trees (the family trees of branching processes) that settle several conjectures from the literature. Moreover, we define a partial ordering on degree sequences and show that it induces a stochastic ordering on the heights of uniformly random trees with given degree sequences. The latter result implies that sub-binary random trees are stochastically the tallest trees with a given number of vertices and leaves.

Secondly, we consider the strongly connected components (SCCs) of a uniform directed graph on n vertices with i.i.d. in- and out-degree pairs distributed as (D−, D+), with E[D^+] = E[D^_−] = μ. We condition on equal total in- and out-degree. A phase transition for the emergence of a giant SCC is known to occur at the critical point where E[D^−D^+] = μ. We study the model at this critical point and show that, under some additional finite moment conditions, the SCCs ranked by decreasing number of edges with distances rescaled by n^{−1/3} converge in distribution to a sequence of finite strongly connected directed multigraphs with edge lengths, and that these are either 3-regular or loops almost surely. This is the first universality result for the scaling limit of a critical directed graph model and the first quantitative result on the directed configuration model at criticality.

Authors: Donderwinkel, S

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: scaling limit; Galton-Watson trees; directed graphs; Bienayme trees; height of random trees; configuration model; random graphs; random trees
• Subjects: Asymptotic distribution (Probability theory); Limit theorems (Probability theory); Trees (Graph theory); Random graphs