The theory of random graphs

Lecture II. Introductory material

The models

We shall start with some basic facts about the binomial distribution. We shall then introduce the main models of interest to us: G(n,p) and G(n,M). In the first model, we have n labelled vertices and the (ⁿ₂) edges are present with probability p each, with all these events independent. In the second model, we have all the (^(n₂)_M) graphs with M edges on a fixed n vertex set equiprobable.

A third model we shall consider captures the notion of random evolution. Let N=(ⁿ₂). Let (G_t)_t=0^N be defined as follows. Fix an n element set V as the vertex set of our evolving graph. Pick a random permutation e₁,…,e_N of the edges of the complete graph on V, uniformly at random. For 0≤t≤N, let G_t be the graph on V with edge set {e₁,…,e_t}. This defines a random process that starts with the empty graph G₀ and evolves to the complete graph G_N.

Theorems relating the models above will be proved.

Jumbledness and expansion

A key property of random graphs is that their edges are `jumbled'. In fact, we shall prove the following result. Let us say that a graph G on n vertices is (p,A)-uniform if, for d = pn, we have

|e_G(U,W) - p|U||W||≤A√(d|U||W|)

for all disjoint sets U, W⊂V(G) such that 1≤|U|≤|W|≤d|U|.

Theorem 1. For every 0<p=p(n)≤1 the random graph G(n,p) is (p,20)-uniform almost surely.

For convenience, the expression almost surely is used to mean `with probability tending to 1 as n→∞'. We shall also use expressions such as almost every and almost certainly.

As we shall see, one important consequence of Theorem 1 and of results of similar nature is that random graphs are `expanding': `small' sets have large neighbourhoods. In fact, even subgraphs of random graphs are expanding, as long as they satisfy, say, a minimal degree condition.

Threshold phenomena

To give the flavour of many results in the area, we shall prove the following theorem. Given an increasing property of graphs P and a random graph process G=(G_t)_t=0^N, let the hitting time τ(P)=τ(G,P) of P in G be defined as

τ(P)=τ(G,P)=min{t:G_t has P},

where we suppose that the complete graph has P.

Theorem 2. For almost every random graph process, the hitting times of the property of being connected and having positive minimum degree coincide.

Formally, writing conn for the property of being connected and δ>0 for the property of having positive minimum degree, we have that, for almost every G,

τ(G,conn)=τ(G,δ>0).

In other words, typically, when the evolving random graph G_t loses its isolated vertices, it becomes connected.

As it turns out, the hitting times in Theorem 2 are `concentrated' (fluctuate little). In fact, we shall see that increasing properties admit what is called a `threshold', which roughly means that increasing properties appear quite suddenly, at predictable stages, in typical random graph processes (G_t)_t=0^N.

The emergence of the giant component

For a graph G, write let L_k(G) for the number of vertices in the kth largest component. We shall prove the following unexpected result.

Theorem 3. Let ε>0 be fixed. For almost every random graph process G=(G_t)_t=0^N, the following holds: (i) we have L₁(G_t)=o(n) for all t≤(1/2-ε)n and (ii) we have L₁(G_t)≥cn and L₂(G_t)=o(n) for all t≥(1/2+ε)n, where c=c(ε) is a constant that depends only on ε.

Thus, at around time t=n/2, our evolving graph G_t suffers a sudden change in structure: the so called giant component emerges. Far sharper forms of Theorem 3 will be discussed.

Lecture IV. Properties of random graphs

Subgraph containment: small graphs

Classical results in the theory of random graphs concern the existence of small subgraphs in random graphs. Fix a graph H, and let {H⊂G} denote the property that G contains H as a subgraph. The question is then to investigate the hitting time τ(G,H⊂G) of this property. This question, which has an elegant answer, will be studied.

Subgraph containment: large graphs

What if we consider graphs H that are `large' in comparison with G? For instance, what if H is a perfect matching (n/2 independent edges, supposing n even). We shall consider this problem, as well as the problems in which H is a long path (cn edges, with c>0 constant), H is a Hamilton cycle, and, finally, when H is a bounded degree graph with n vertices. To investigate this last, spanning case, we shall consider a method due to Alon and Füredi. Furthermore, results of Riordan will be discussed.

Other graph parameters

Other classical graph parameters will also be studied. In particular, we shall discuss the clique number, the chromatic number, the diameter, and the connectivity of random graphs. A phenomenon that will be of particular interest is the high concentration of these parameters. General tools for proving concentration of random variables will be discussed.

Lecture VI. Extremal problems

Ramsey and Turán type results

Write G→(H)_r if the graph G has the following Ramsey type property: any r-edge colouring of G contains a monochromatic copy of the graph H. For instance, the well known fact that any 2-colouring of the complete graph on 6 vertices contains a monochromatic triangle may be expressed as K⁶→(K³)₂.

Furthermore, write G→_ρ H if any ρ-fraction of the edges of G spans a subgraph that contains H. This is the `density' or `extremal' counterpart to the Ramsey property described above.

We shall consider both the Ramsey and extremal properties for fixed graphs H and we shall ask when a random graph has those properties. We shall prove the following theorems.

Theorem 4. Let r be an integer. If C is a large enough constant, the random graph G(n,p) with p=p(n)=C/√n almost surely has the Ramsey property G(n,p)→(K³)_r.

Theorem 5. Let δ>0 be a fixed real number. If C is a large enough constant, the random graph G(n,p) with p=p(n)=C/√n almost surely has the extremal property G(n,p)→_1/2+δK³.

The theorems above imply, among others, the existence of K⁴-free graphs G with the Ramsey and density properties above.

Szemerédi's regularity lemma

A tool that is often useful in approaching results such as the ones given in Theorems 4 and 5 is the regularity lemma of Szemerédi, suitably adapted to this context. We shall discuss how ideas similar to the ones used in classical applications of the regularity lemma transfer to the random graphs setting.