Component sizes in random graphs

Abstract

In this thesis we are interested in establishing upper bounds for the probability of observing unusually large components in some models of random graphs at criticality.

More precisely, given a certain (undirected) random graph G on n vertices, our main purpose is to provide bounds for probabilities like

P( C(Vn)> k) and P(Cmax> k) (1)

where C(Vn) represents the component of a node Vn selected uniformly at random from the vertex set 1 n , Cmax represents a maximal component in the random graph G and k An2 3, with n2 3 being the correct size of Cmax for the specific models studied here, and A a (large) quantity which may depend on n.

We start by presenting our main results in Chapter 1. These are three theorems which serve different purposes. With the rst two results we establish the correct asymptotic order of the probabilities in (1) for near-critical Erdos-Renyi random graphs and for near-critical percolation on random regular graphs. On the other, our last theorem is a simple, yet general result which provides polynomial upper bounds for the probabilities in (1) for several random graphs when considered at criticality.

In Chapter 2 we state a few preliminary results which are needed to prove the theorems presented in Chapter 1. Speci cally, we start this chapter by stating a few known facts, and subsequently we introduce new ballot-type estimates which constitute a key ingredient in the proofs of all our upper bounds.

We proceed with Chapter 3, where we describe the martingale method of Nachmias and Peres [44]. Speci cally, we show how their technique leads to exponential upper bounds for the probabilities in (1), bounds which are not optimal and that we subsequently improve in Chapter 4 through our new methodology.

More speci cally, in Chapter 4, we prove our result concerning the near-critical Erdos-Renyi random graph, namely we derive matching upper and lower bounds for both the probabilities in (1).

We continue with Chapter 5, where we adapt the methodology introduced in Chapter 4 to derive the correct asymptotic order of the probabilities in (1) for near-critical percolation on random regular graphs.

We conclude with Chapter 6, where we show that part of the method used in the previous two chapters can be used to obtain polynomial upper bounds for the probabilities in (1) in several models of random graphs when considered at criticality.

The results which we present in this thesis are based on the following three papers:

1. Unusually large components in near-critical Erdos-Renyi graphs via ballot theorems (with Matthew I. Roberts). Accepted by Combinatorics, Probability and Computing (2021);
2. An elementary approach to component sizes in critical random graphs. Accepted with minor revision by Journal of Applied Probability (2021);
3. The probability of unusually large components for critical percolation on random d regular graphs (with Matthew I. Roberts). Preprint (2021).

Date of Award	25 May 2022
Original language	English
Awarding Institution	University of Bath
Supervisor	Matt Roberts (Supervisor) & Cecile Mailler (Supervisor)