Matthew Coulson
defended his PhD thesis Threshold phenomena involving the connected components of random graphs and digraphs (pdf), supervised by Guillem Perarnau (IMTech & DMAT), on 13 December 2021 within the UPC doctoral program in Applied Mathematics at the FME. Currently he is a postdoctoral researcher at University of Waterloo in Canada working with Luke Postle.
The investigation reported in this thesis is about the behavior of some models of random graphs and directed graphs near thresholds for the appearance of certain types of connected components.
Thesis Summary
In the first chapter, the focus is the study of the critical window for the appearance of a giant strongly connected component in binomial random digraphs. Bounds on the probability that the largest strongly connected component is very large or very small are provided. These bounds improve results of T. Łuczak and T. G. Seierstad [2]. The main result is based on a careful analysis of an exploration process.
In the second chapter, the configuration model in the subcritical and barely subcritical ranges is explored. New upper bounds on the size of the largest connected component are obtained. The proofs rely on a new local limit theorem for the sum of independent random variables, which gives explicit error bounds. There are also examples showing that such bounds are tight for some instances.
The last two chapters are devoted to the study of the directed configuration model, a popular model for random digraphs. First, the investigation of the barely subcritical region yields that this model behaves similarly to the binomial random digraph. The main result is a Poisson approximation for the number of long directed cycles in the graph. Finally, the problem of determining a threshold for the existence of a giant weak component in the model is examined, and the outcome goes beyond non-formal results on the topic previously obtained by I. Kryven [3].
Highlighted publication: [1].
References
[1] M. Coulson. The critical window in random digraphs. Combinatorics, Probability and Computing 31.3 (2022), 411-429.
[2] T. Łuczak and T. G. Seierstad. The critical behavior of random digraphs. Random Structures & Algorithms, 35.3 (2009), 271-293.
[3] I. Kryven. Emergence of the giant weak component in directed random graphs with arbitrary degree distributions. Phys RevE, 94.1 (2016), 012315.