Introduction To Random Graphs
Introduction To Random Graphs
I Basic Models 1
1 Random Graphs 3
1.1 Models and Relationships . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thresholds and Sharp Thresholds . . . . . . . . . . . . . . . . . . 9
1.3 Pseudo-Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Evolution 21
2.1 Sub-Critical Phase . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Super-Critical Phase . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Phase Transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3 Vertex Degrees 51
3.1 Degrees of Sparse Random Graphs . . . . . . . . . . . . . . . . . 51
3.2 Degrees of Dense Random Graphs . . . . . . . . . . . . . . . . . 57
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4 Connectivity 67
4.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 k-connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Small Subgraphs 75
5.1 Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Asymptotic Distributions . . . . . . . . . . . . . . . . . . . . . . 79
5.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
ii Contents
5.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6 Spanning Subgraphs 89
6.1 Perfect Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.3 Long Paths and Cycles in Sparse Random Graphs . . . . . . . . . 101
6.4 Greedy Matching Algorithm . . . . . . . . . . . . . . . . . . . . 103
6.5 Random Subgraphs of Graphs with Large Minimum Degree . . . 107
6.6 Spanning Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . 110
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
11 Digraphs 239
11.1 Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . 239
11.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 247
11.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
11.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
12 Hypergraphs 253
12.1 Component Size . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
12.2 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 258
12.3 Perfect matchings in r-regular s-uniform hypergraphs . . . . . . . 262
12.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
12.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
16 Mappings 347
16.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
16.2 Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
16.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
16.4 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
17 k-out 361
17.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
17.2 Perfect Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . 364
17.3 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 373
17.4 Nearest Neighbor Graphs . . . . . . . . . . . . . . . . . . . . . . 376
17.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
17.6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
22 Thresholds 471
22.1 The Kahn-Kalai conjecture . . . . . . . . . . . . . . . . . . . . . 474
22.2 Proof of the Kahn-Kalai conjecture . . . . . . . . . . . . . . . . . 475
22.3 Constructing a cover . . . . . . . . . . . . . . . . . . . . . . . . 475
22.4 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
22.5 Square of a Hamilton cycle and a little more . . . . . . . . . . . . 479
22.6 Embedding a factor . . . . . . . . . . . . . . . . . . . . . . . . . 481
22.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
22.8 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
23 Contiguity 487
23.1 Small subgraph conditioning for proving contiguity . . . . . . . . 488
23.2 Contiguity of random regular graphs and multigraphs . . . . . . . 493
23.3 Contiguity of superposition models . . . . . . . . . . . . . . . . . 497
23.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
23.5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
27 Inequalities 543
27.1 Binomial Coefficient Approximation . . . . . . . . . . . . . . . . 543
27.2 Balls in Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
27.3 FKG Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
27.4 Sums of Independent Bounded Random Variables . . . . . . . . . 547
27.5 Sampling Without Replacement . . . . . . . . . . . . . . . . . . 553
27.6 Janson’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . 554
27.7 Martingales. Azuma-Hoeffding Bounds . . . . . . . . . . . . . . 556
27.8 Talagrand’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . 563
27.9 Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
31 Entropy 589
31.1 Basic Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
31.2 Shearer’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 592
32 Indices 657
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
Main Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
Preface
History
Random graphs were used by Erdős [330] to give a probabilistic construction of
a graph with large girth and large chromatic number. It was only later that Erdős
and Rényi began a systematic study of random graphs as objects of interest in their
own right. Early on they defined the random graph Gn,m and founded the subject.
Often neglected in this story is the contribution of Gilbert [433] who introduced
the model Gn,p , but clearly the credit for getting the subject off the ground goes to
Erdős and Rényi. Their seminal series of papers [331], [333], [334], [335] and in
particular [332], on the evolution of random graphs laid the groundwork for other
mathematicians to become involved in studying properties of random graphs.
In the early eighties the subject was beginning to blossom and it received a
boost from two sources. First was the publication of the landmark book of Béla
Bollobás [155] on random graphs. Around the same time, the Discrete Mathemat-
ics group in Adam Mickiewicz University began a series of conferences in 1983.
This series continues biennially to this day and is now a conference attracting
more and more participants.
The next important event in the subject was the start of the journal Random
Structures and Algorithms in 1990 followed by Combinatorics, Probability and
viii Contents
Computing a few years later. These journals provided a dedicated outlet for work
in the area and are flourishing today.
Acknowledgement
Several people have helped with the writing of this book and we would like to
acknowledge their help. First there are the students who have sat in on courses
based on early versions of this book and who helped to iron out the many typo’s
etc.
We would next like to thank the following people for reading parts of the
book before final submission: Andrew Beveridge, Deepak Bal, Malgosia Bed-
narska, Patrick Bennett, Mindaugas Blozneliz, Antony Bonato, Boris Bukh, Fan
Chung, Amin Coja-Oghlan, Colin Cooper, Andrzej Dudek, Asaf Ferber, Nikolas
Fountoulakis, Catherine Greenhill, Dan Hefetz, Paul Horn, Hsien–Kuei Hwang,
Tal Hershko, Jerzy Jaworski, Tony Johansson, Mihyun Kang, Michael Krivele-
vich, Tomasz Łuczak, Colin McDiarmid, Andrew McDowell, Hosam Mahmoud,
Contents ix
Mike Molloy, Tobias Müller, Rajko Nenadov, Wesley Pegden, Huy Pham, Boris
Pittel, Dan Poole, Pawel Prałat, Oliver Riordan, Andrzej Ruciński, Katarzyna Ry-
barczyk, Wojtek Samotij, Yilun Shang, Matas Šilekis, Greg Sorkin, Joel Spencer,
Sam Spiro, Dudley Stark, Angelika Steger, Prasad Tetali, Andrew Thomason, Lin-
nus Wästlund, Nick Wormald, Stephen Young.
Thanks also to Béla Bollobás for his advice on the structure of the book.
Conventions/Notation
Often in what follows, we will give an expression for a large positive integer. It
might not be obvious that the expression is actually an integer. In which case, the
reader can rest assured that he/she can round up or down and obtained any required
property. We avoid this rounding for convenience and for notational purposes.
In addition we list the following notation:
Mathematical Relations
• f (x) = O(g(x)): | f (x)| ≤ K|g(x)| for some constant K > 0 and all x ∈ R.
• f (x) = Ω(g(x)) if f (x) ≥ cg(x) for some positive constant c.0 and all x ∈ R.
• A B: A/B → 0 as n → ∞.
• A B: A/B → ∞ as n → ∞.
• A . B or B & A if A ≤ (1 + o(1))B.
• [n]: This is {1, 2, . . . , n}. In general, if a < b are positive integers, then
[a, b] = {a, a + 1, . . . , b}.
Graph Notation
x Contents
• G = (V, E): V = V (G) is the vertex set and E = E(G) is the edge set.
• e(G) = |E(G)| and for S ⊆ V we have eG (S) = | {e ∈ E : e ⊆ S} |.
• For S, T ⊆ V, S ∩ T = 0/ we have eG (S : T ) = {e = {x, y} ∈ E : x ∈ S, y ∈ T }.
• N(S) = NG (S) = {w ∈
/ S : ∃v ∈ S such that {v, w} ∈ E} and dG (S) = |NG (S)|
for S ⊆ V (G).
• NG (S, X) = NG (S) ∩ X for X, S ⊆ V .
• degS (x) = | {y ∈ S : {x, y} ∈ E} | for x ∈ V, S ⊆ V and deg(v) = degV (v).
• For sets X,Y ⊆ V (G) we let NG (X,Y ) = {y ∈ Y : ∃x ∈ X, {x, y} ∈ E(G)}
and eG (X,Y ) = |NG (X,Y )|.
• For a graph H, aut(H) denotes the number of automorphisms of H.
• dist(v, w) denotes the graph distance between vertices v, w.
• The co-degree of vertices v, w of graph G is NG (v) ∩ NG (w).
Random Graph Models
• [n]: The set {1, 2, . . . , n}.
• Gn,m : The family of all labeled graphs with vertex set V = [n] = {1, 2, . . . , n}
and exactly m edges.
• Gn,m :A random graph chosen uniformly at random from Gn,m .
• En,m = E(Gn,m ).
• Gn,p : A random graph on vertex set [n] where each possible edge occurs
independently with probability p.
• En,p = E(Gn,p ).
≥k : G
• Gδn,m n,m , conditioned on having minimum degree at least k.
• Gn,n,p : A random bipartite graph with vertex set consisting of two disjoint
copies of [n] where each of the n2 possible edges occurs independently with
probability p.
• Gn,r : A random r-regular graph on vertex set [n].
• Gn,d : The set of graphs with vertex set [n] and degree sequence
d = (d1 , d2 , . . . , dn ).
Contents xi
• Hn,p;k : A random k-uniform hypergraph on vertex set [n] where each of the
n
k possibles edge occurs independently with probability p.
• ~Gk−out : A random digraph on vertex set [n] where each v ∈ [n] indepen-
dently chooses k random out-neighbors.
• Gk−out : The graph obtained from ~Gk−out by ignoring orientation and coa-
lescing multiple edges.
Probability
• N(0, 1): A random variable with the normal distribution, mean 0 and vari-
ance 1.
• Bin(n, p): A random variable with the binomial distribution with parameters
n, the number of trials and p, the probability of success.
Basic Models
Chapter 1
Random Graphs
Graph theory is a vast subject in which the goals are to relate various graph prop-
erties i.e. proving that Property A implies Property B for various properties A,B.
In some sense, the goals of Random Graph theory are to prove results of the form
“Property A almost always implies Property B”. In many cases Property A could
simply be “Graph G has m edges”. A more interesting example would be the fol-
lowing: Property A is “G is an r-regular graph, r ≥ 3” and Property B is “G is
r-connected”. This is proved in Chapter 9.
Before studying questions such as these, we will need to describe the basic
models of a random graph.
assign a probability
n−1
P(G) = 2 .
m
Equivalently, we start with an empty graph on the set [n], and insert m edges
n
in such a way that all possible (m2) choices are equally likely. We denote such a
random graph by Gn,m = ([n], En,m ) and call it a uniform random graph.
We now describe a similar model. Fix 0 ≤ p ≤ 1. Then for 0 ≤ m ≤ n2 , assign
to each graph G with vertex set [n] and m edges a probability
n
P(G) = pm (1 − p)(2)−m ,
4 Chapter 1. Random Graphs
where 0 ≤ p ≤1. Equivalently, we start with an empty graph with vertex set [n]
and perform n2 Bernoulli experiments inserting edges independently with proba-
bility p. We call such a random graph, a binomial random graph and denote it by
Gn,p = ([n], En,p ). This was introduced by Gilbert [433]
As one may expect there is a close relationship between these two models of
random graphs. We start with a simple observation.
Lemma 1.1. A random graph Gn,p , given that its number of edges is m, is equally
n
likely to be one of the (2) graphs that have m edges.
m
{Gn,p = G0 } ⊆ {|En,p | = m}
we have
P(Gn,p = G0 , |En,p | = m)
P(Gn,p = G0 | |En,p | = m) =
P(|En,p | = m)
P(Gn,p = G0 )
=
P(|En,p | = m)
n
pm (1 − p)(2)−m
= n
(2) pm (1 − p)(n2)−m
m
n−1
= 2 .
m
Thus Gn,p conditioned on the event {Gn,p has m edges} is equal in distribu-
tion to Gn,m , the graph chosen uniformly at random from all graphs with m edges.
Obviously, the main difference between those two models of random graphs is that
in Gn,m we choose its number of edges, while in the case of Gn,p the number of
edges is the Binomial random variable with the parameters n2 and p. Intuitively,
for large n random graphs Gn,m and Gn,p should behave in a similar fashion when
the number of edges m in Gn,m equals or is “close” to the expected number of
edges of Gn,p , i.e., when
n2 p
n
m= p≈ , (1.1)
2 2
or, equivalently, when the edge probability in Gn,p
2m
p≈ . (1.2)
n2
1.1. Models and Relationships 5
1 − p = (1 − p1 )(1 − p2 ), (1.3)
or, equivalently,
p = p1 + p2 − p1 p2 .
Thus an edge is not included in Gn,p if it is not included in either of Gn,p1 or Gn,p2 .
It follows that
Gn,p = Gn,p1 ∪ Gn,p2 ,
where the two graphs Gn,p1 , Gn,p2 are independent. So when we write
Gn,p1 ⊆ Gn,p ,
we mean that the two graphs are coupled so that Gn,p is obtained from Gn,p1 by
superimposing it with Gn,p2 and replacing eventual double edges by a single one.
We can also couple random graphs Gn,m1 and Gn,m2 where m2 ≥ m1 via
Gn,m2 = Gn,m1 ∪ H.
Here H is the random graph on vertex set [n] that has m = m2 − m1 edges chosen
uniformly at random from [n]
2 \ En,m1 .
Consider now a graph property P defined as a subset of the set of all labeled
n
graphs on vertex set [n], i.e., P ⊆ 2(2) . For example, all connected graphs (on n
vertices), graphs with a Hamiltonian cycle, graphs containing a given subgraph,
planar graphs, and graphs with a vertex of given degree form a specific “graph
property”.
We will state below two simple observations which show a general relation-
ship between Gn,m and Gn,p in the context of the probabilities of having a given
graph property P. The constant 10 in the next lemma is not best possible, but in
the context of the usage of the lemma, any constant will suffice.
Next recall that the number of edges |En,p | of a random graph Gn,p is a random
variable with the Binomial distribution with parameters n2 and p. Applying Stir-
ling’s Formula:
k
k √
k! = (1 + o(1)) 2πk, (1.5)
e
and putting N = n2 , we get, after substituting (1.5) for the factorials in Nm ,
N m n
P(|En,p | = m) = p (1 − p)(2)−m
m
√
N N 2πN pm (1 − p)N−m
= (1 + o(1)) p (1.6)
mm (N − m)N−m 2π m(N − m)
s
N
= (1 + o(1)) ,
2πm(N − m)
Hence
1
P(|En,p | = m) ≥ √ ,
10 m
so
P(Gn,m ∈ P) ≤ 10m1/2 P(Gn,p ∈ P).
1.1. Models and Relationships 7
and
P(Gn,m ∈ P) ≤ P(Gn,m0 ∈ P), (1.8)
respectively.
For monotone increasing graph properties we can get a much better upper bound
on P(Gn,m ∈ P), in terms of P(Gn,p ∈ P), than that given by Lemma 1.2.
N
P(Gn,p ∈ P) = ∑ P(Gn,k ∈ P) P(|En,p| = k)
k=0
N
≥ ∑ P(Gn,k ∈ P) P(|En,p| = k)
k=m
The number of edges |En,p | in Gn,p has the Binomial distribution with parameters
N, p. Hence
N
P(Gn,p ∈ P) ≥ P(Gn,m ∈ P) ∑ P(|En,p| = k)
k=m
N
= P(Gn,m ∈ P) ∑ uk , (1.9)
k=m
where
N k
uk = p (1 − p)N−k .
k
Now, using Stirling’s formula,
N N pm (1 − p)N−m 1 + o(1)
um = (1 + o(1)) 1/2
= .
m
m (N − m) N−m (2πm) (2πm)1/2
after using Lemma 27.1(a),(b) to obtain the inequality. and our assumptions on
N, p to obtain the second.
It follows that for 0 ≤ t ≤ m1/2 ,
( )
t−1
1 + o(1) s s+1
um+t ≥ exp − ∑ − ≥
(2πm)1/2 s=0 N − m − s m
n 2 o
t
exp − 2m − o(1)
,
(2πm)1/2
other situations we can use a stronger and more widely applicable result. The
theorem below, which we state without proof, gives precise conditions for the
asymptotic equivalence of random graphs Gn,p and Gn,m . It is due to Łuczak
[632].
p
Theorem 1.4. Let 0 ≤ p0 ≤ 1, s(n) = n p(1 − p) → ∞, and ω(n) → ∞ arbitrarily
slowly as n → ∞.
(i) Suppose that P is a graph property such that P(Gn,m ∈ P) → p0 for all
n n
m∈ p − ω(n)s(n), p + ω(n)s(n) .
2 2
Then P(Gn,p ∈ P) → p0 as n → ∞,
as n → ∞.
P(Gn,p(ε) ∈ P) = ε.
Gn,1−(1−p)k ⊆ Gn,kp ,
/ P implies G1 , G2 , . . . , Gk ∈
and so Gn,kp ∈ / P. Hence
/ P) ≤ [P(Gn,p ∈
P(Gn,kp ∈ / P)]k .
1.2. Thresholds and Sharp Thresholds 11
/ P) ≤ 2−ω = o(1).
P(Gn,ω p∗ ∈
lim P(En ) = 1.
n→∞
Thus the statement that says p∗ is a threshold for a property P in Gn,p is the same
as saying that Gn,p 6∈ P w.h.p. if p p∗ , while Gn,p ∈ P w.h.p. if p p∗ .
In many situations we can observe that for some monotone graph properties
more “subtle” thresholds hold. We call them “sharp thresholds”. More precisely,
Definition 1.8. A function m∗ = m∗ (n) is a sharp threshold for a monotone in-
creasing property P in the random graph Gn,m if for every ε > 0,
0 i f m/m∗ ≤ 1 − ε
lim P(Gn,m ∈ P) =
n→∞ 1 i f m/m∗ ≥ 1 + ε.
0 i f p/p∗ ≤ 1 − ε
lim P(Gn,p ∈ P) =
n→∞ 1 i f p/p∗ ≥ 1 + ε.
This simple graph property is clearly monotone increasing and we will show be-
low that p∗ = 1/n2 is a threshold for a random graph Gn,p of having at least one
edge (being non-empty).
Lemma 1.10. Let P be the property defined above, i.e., stating that Gn,p contains
at least one edge. Then
(
0 if p n−2
lim P(Gn,p ∈ P) =
n→∞ 1 if p n−2 .
Proof. Let X be a random variable counting edgesin Gn,p . Since X has the Bino-
mial distribution, then E X = 2 p, and Var X = n2 p(1 − p) = (1 − p) E X.
n
A standard way to show the first part of the threshold statement, i.e. that w.h.p.
a random graph Gn,p is empty when p = o(n−2 ), is a very simple consequence of
the Markov inequality, called the First Moment Method, see Lemma 26.2. It states
that if X is a non-negative integer valued random variable, then
Var X
P(X > 0) ≥ 1 − .
(E X)2
Consider the monotone decreasing graph property that a graph contains an isolated
vertex, i.e. a vertex of degree zero:
We will show that m∗ = 21 n log n is the sharp threshold function for the above
property P in Gn,m .
Lemma 1.11. Let P be the property that a graph on n vertices contains at least
one isolated vertex and let m = 21 n(log n + ω(n)). Then
(
1 if ω(n) → −∞
lim P(Gn,m ∈ P) =
n→∞ 0 if ω(n) → ∞.
Proof. To see that the second statement of Lemma 1.11 holds we use the First
Moment Method. Namely, let X0 = Xn,0 be the number of isolated vertices in the
random graph Gn,m . Then X0 can be represented as the sum of indicator random
variables
X0 = ∑ Iv ,
v∈V
where (
1 if v is an isolated vertex in Gn,m
Iv =
0 otherwise.
14 Chapter 1. Random Graphs
So
(n−1
2 )
m
E X0 = ∑ E Iv = n n =
v∈V
() 2
m
m m−1
n−2 4i
n ∏ 1− =
n i=0 n(n − 1)(n − 2) − 2i(n − 2)
n−2 m (log n)2
n 1+O , (1.10)
n n
assuming that ω = o(log n).
(For the product we use 1 ≥ ∏m−1 m−1
i=0 (1 − xi ) ≥ 1 − ∑i=0 xi which is valid for all
0 ≤ x0 , x1 , . . . , xm−1 ≤ 1.)
Hence,
n−2 m
2m
E X0 ≤ n ≤ ne− n = e−ω ,
n
for m = 12 n(log n + ω(n)).
(1 + x ≤ ex is one of the basic inequalities stated in Lemma 27.1.)
So E X0 → 0 when ω(n) → ∞ as n → ∞ and the First Moment Method implies
that X0 = 0 w.h.p.
To show that Lemma 1.11 holds in the case when ω → −∞ we first observe
from (1.10) that in this case
n−2 m
E X0 = (1 − o(1))n
n
2m
≥ (1 − o(1))n exp −
n−2
−ω
≥ (1 − o(1))e → ∞, (1.11)
The second inequality in the above comes from Lemma 27.1(b), and we have once
again assumed that ω = o(log n) to justify the first equation.
We caution the reader that E X0 → ∞ does not prove that X0 > 0 w.h.p. In
Chapter 5 we will see an example of a random variable XH , where E XH → ∞ and
yet XH = 0 w.h.p.
We will now use a stronger version of the Second Moment Method (for its
proof see Section 26.1 of Chapter 26). It states that if X is a non-negative integer
valued random variable then
(E X)2 Var X
P(X > 0) ≥ 2
= 1− . (1.12)
EX EX2
Notice that
1.2. Thresholds and Sharp Thresholds 15
!2
E X02 = E ∑ Iv = ∑ E(Iu Iv )
v∈V u,v∈V
= ∑ P(Iu = 1, Iv = 1)
u,v∈V
= ∑ P(Iu = 1, Iv = 1) + ∑ P(Iu = 1, Iv = 1)
u6=v u=v
n−2
( ) 2
= n(n − 1) mn + E X0
() 2
m
2m
n−2
≤ n2 + E X0
n
= (1 + o(1))(E X0 )2 + E X0 .
The last equation follows from (1.10).
Hence, by (1.12),
(E X0 )2
P(X0 > 0) ≥
E X02
(E X0 )2
≥
(1 + o(1))((E X0 )2 + E X0 )
1
=
(1 + o(1) + (E X0 )−1
= 1 − o(1),
on using (1.11). Hence P(X0 > 0) → 1 when ω(n) → −∞ as n → ∞, and so we can
conclude that m = m(n) is the sharp threshold for the property that Gn,m contains
isolated vertices.
For this simple random variable, we worked with Gn,m . We will in general
work with the more congenial independent model Gn,p and translate the results to
Gn,m if so desired.
For another simple example of the use of the second moment method, we will
prove
Theorem 1.12. If m/n → ∞ then w.h.p. Gn,m contains at least one triangle.
Proof. Because having a triangle is a monotone increasing property we can prove
the result in Gn,p assuming that np → ∞.
Assume first that np = ω ≤ log n where ω = ω(n) → ∞ and let Z be the number
of triangles in Gn,p . Then
ω3
n 3
EZ = p ≥ (1 − o(1)) → ∞.
3 6
16 Chapter 1. Random Graphs
We remind the reader that simply having E Z → ∞ is not sufficient to prove that
Z > 0 w.h.p.
Next let T1 , T2 , . . . , TM , M = n3 denote the triangles of Kn . Then
M
E Z2 = ∑ P(Ti , T j ∈ Gn,p )
i, j=1
M M
= ∑ P(Ti ∈ Gn,p ) ∑ P(T j ∈ Gn,p | Ti ∈ Gn,p ) (1.13)
i=1 j=1
M
= M P(T1 ∈ Gn,p ) ∑ P(T j ∈ Gn,p | T1 ∈ Gn,p ) (1.14)
j=1
M
= E Z × ∑ P(T j ∈ Gn,p | T1 ∈ Gn,p ).
j=1
This proves the theorem for p ≤ logn n . For larger p we can use (1.7).
We can in fact use the second moment method to show that if m/n → ∞ then
w.h.p. Gn,m contains a copy of a k-cycle Ck for any fixed k ≥ 3. See Theorem 5.3,
see also Exercise 1.4.7.
1.3. Pseudo-Graphs 17
1.3 Pseudo-Graphs
We sometimes use one of the two the following models that are related to Gn,m
and have a little more independence. (We will use Model A in Section 7.3 and
Model B in Section 6.4).
Model A: We let x = (x1 , x2 , . . . , x2m ) be chosen uniformly at random from
[n]2m .
Model B: We let x = (x1 , x2 , . . . , x2m ) be chosen uniformly at random from
[n]m
2 .
(X)
The (multi-)graph Gn,m , X ∈ {A, B} has vertex set [n] and edge set Em =
{{x2i−1 , x2i } : 1 ≤ i ≤ m}. Basically, we are choosing edges with replacement. In
Model A we allow loops and in Model B we do not. We get simple graphs from
(X∗)
by removing loops and multiple edges to obtain graphs Gn,m with m∗ edges. It
is not difficult to see that for X ∈ {A, B} and conditional on the value of m∗ that
(X∗)
Gn,m is distributed as Gn,m∗ , see Exercise (1.4.11).
More importantly, we have that for G1 , G2 ∈ Gn,m ,
(X) (X) (X) (X)
P(Gn,m = G1 | Gn,m is simple) = P(Gn,m = G2 | Gn,m is simple), (1.15)
for X = A, B.
This is because for i = 1, 2,
Indeed, we can permute the edges in m! ways and permute the vertices within
(X)
edges in 2m ways without changing the underlying graph. This relies on Gn,m
being simple.
Secondly, if m = cn for a constant c > 0 then with N = n2 , and using Lemma
27.2,
N m!2m
(X)
P(Gn,m is simple) ≥ ≥
m n2m
Nm m2 m3 m!2m
(1 − o(1)) exp − −
m! 2N 6N 2 n2m
2 +c)
= (1 − o(1))e−(c . (1.16)
(X) (X)
P(Gn,m ∈ P) = P(Gn,m ∈ P | Gn,m is simple) ≤
18 Chapter 1. Random Graphs
2 +c (X)
(1 + o(1))ec P(Gn,m ∈ P). (1.17)
Here we have used the inequality P(A | B) ≤ P(A)/ P(B) for events A, B.
(X)
We will use this model a couple of times and (1.17) shows that if P(Gn,m ∈
P) = o(1) then P(Gn,m ∈ P) = o(1), for m = O(n).
(A)
Model Gn,m was introduced independently by Bollobás and Frieze [166] and
by Chvátal [229].
1.4 Exercises
We point out here that in the following exercises, we have not asked for best pos-
sible results. These exercises are for practise. You will need to use the inequalities
from Section 27.1.
1.4.1 Suppose that p = d/n where d = o(n1/3 ). Show that w.h.p. Gn,p has no
copies of K4 .
1.4.2 Suppose that p = d/n where d > 1. Show that w.h.p. Gn,p contains an
induced path of length (log n)1/2 .
1.4.3 Suppose that p = d/n where d = O(1). Prove that w.h.p., in Gn,p , for all
S ⊆ [n], |S| ≤ n/ log n, we have e(S) ≤ 2|S|, where e(S) is the number of
edges contained in S.
1.4.4 Suppose that p = log n/n. Let a vertex of Gn,p be small if its degree is less
than log n/100. Show that w.h.p. there is no edge of Gn,p joining two small
vertices.
1.4.5 Suppose that p = d/n where d is constant. Prove that w.h.p., in Gn,p , no
vertex belongs to more than one triangle.
1.4.6 Suppose that p = d/n where
l d is constant.
m Prove that w.h.p. Gn,p contains
a vertex of degree exactly (log n)1/2 .
1.4.7 Suppose that k ≥ 3 is constant and that np → ∞. Show that w.h.p. Gn,p
contains a copy of the k-cycle, Ck .
1.4.8 Suppose that 0 < p < 1 is constant. Show that w.h.p. Gn,p has diameter
two.
1.4.9 Let f : [n] → [n] be chosen uniformly at random from all nn functions from
[n] → [n]. Let X = { j :6 ∃i s.t. f (i) = j}. Show that w.h.p. |X| ≈ e−1 n.
1.5. Notes 19
1.5 Notes
Friedgut and Kalai [378] and Friedgut [379] and Bourgain [185] and Bourgain
and Kalai [184] provide much greater insight into the notion of sharp thresholds.
Friedgut [377] gives a survey of these aspects. For a graph property A let µ(p, A )
be the probability that the random graph Gn,p has property A . A threshold is
)
coarse if it is not sharp. We can identify coarse thresholds with p dµ(p,A dp < C for
some absolute constant 0 < C. The main insight into coarse thresholds is that to
exist, the occurrence of A can in the main be attributed to the existence of one
of a bounded number of small subgraphs. For example, Theorem 2.1 of [377]
states that there exists a function K(C, ε) such that the following holds. Let A be
a monotone property of graphs that is invariant under automorphism and assume
)
that p dµ(p,A
dp < C for some constant 0 < C. Then for every ε > 0 there exists a
finite list of graphs G1 , G2 , . . . , Gm all of which have no more than K(ε,C) edges,
such that if B is the family of graphs having one of these graphs as a subgraph
then µ(p, A ∆B) ≤ ε.
20 Chapter 1. Random Graphs
Chapter 2
Evolution
Here begins our story of the typical growth of a random graph. All the results up
to Section 2.3 were first proved in a landmark paper by Erdős and Rényi [332].
The notion of the evolution of a random graph stems from a dynamic view of a
graph process: viz. a sequence of graphs:
G0 = ([n], 0),
/ G1 , G2 , . . . , Gm , . . . , GN = Kn .
Theorem 2.2. If m n1/2 then Gm is the union of isolated vertices and edges
w.h.p.
Proof. Let p = m/N, m = n1/2 /ω and let X be the number of paths of length two
in the random graph Gn,p . By the First Moment Method,
n4
n 2
P(X > 0) ≤ E X = 3 p ≤ → 0,
3 2N 2 ω 2
2.1. Sub-Critical Phase 23
as n → ∞. Hence
Notice that the property that a graph contains a path of a given length two is
monotone increasing, so by Lemma 1.3,
Proof. Let p = Nm , m = ωn1/2 and X be the number of paths of length two in Gn,p .
Then
n 2
EX = 3 p ≈ 2ω 2 → ∞,
3
as n → ∞. This however does not imply that X > 0 w.h.p.! To show that X > 0
w.h.p. we will apply the Second Moment Method
Let P2 be the set of all paths of length two in the complete graph Kn , and let
X̂ be the number of isolated paths of length two in Gn,p i.e. paths that are also
components of Gn,p . We will show that w.h.p. Gn,p contains such an isolated
path. Now,
X̂ = ∑ IP⊆i Gn,p .
P∈P2
We always use IE to denote the indicator for an event E . The notation ⊆i indicates
that P is contained in Gn,p as a component (i.e. P is isolated). Having a path of
length two is a monotone increasing property. Therefore we can assume that m =
o(n) and so np = o(1) and the result for larger m will follow from monotonicity
and coupling. Then
n 2
E X̂ = 3 p (1 − p)3(n−3)+1
3
n3 4ω 2 n
≥ (1 − o(1)) (1 − 3np) → ∞,
2 n4
as n → ∞.
In order to compute the second moment of the random variable X̂ notice that,
∗
X̂ 2 = ∑ ∑ IP⊆i Gn,p IQ⊆i Gn,p = ∑P,Q∈P IP⊆i Gn,p IQ⊆i Gn,p ,
2
P∈P2 Q∈P2
24 Chapter 2. Evolution
where the last sum is taken over P, Q ∈ P2 such that either P = Q or P and Q are
vertex disjoint. The simplification that provides the last summation is precisely
the reason that we introduce path-components (isolated paths). Now
( )
E X̂ 2 = ∑ ∑ P(Q ⊆i Gn,p| P ⊆i Gn,p) P(P ⊆i Gn,p ).
P Q
The expression inside the brackets is the same for all P and so
where P{1,2,3} denotes the path on vertex set [3] = {1, 2, 3} with middle vertex
2. By conditioning on the event P(1,2,3) ⊆i Gn,p , i.e, assuming that P(1,2,3) is a
component of Gn,p , we see that all of the nine edges between Q and P(1,2,3) must
be missing. Therefore
n 2
2 3(n−6)+1
≤ E X̂ 1 + (1 − p)−9 E X̂ .
E X̂ ≤ E X̂ 1 + 3 p (1 − p)
3
So, by the Second Moment Method (see Lemma 26.5),
(E X̂)2 (E X̂)2
P(X̂ > 0) ≥ ≥
E X̂ 1 + (1 − p)−9 E X̂
E X̂ 2
1
= →1
(1 − p)−9 + [E X̂]−1
as n → ∞, since p → 0 and E X̂ → ∞. Thus
P(Gn,p contains an isolated path of length two) → 1,
which implies that P(Gn,p contains a path of length two) → 1. As the property of
having a path of length two is monotone increasing it in turn implies that
P(Gm contains a path of length two) → 1
for m n1/2 and the theorem follows.
From Theorems 2.2 and 2.3 we obtain the following corollary.
Corollary 2.4. The function m∗ (n) = n1/2 is the threshold for the property that a
random graph Gm contains a path of length two, i.e.,
(
o(1) if m n1/2 .
P(Gm contains a path of length two) =
1 − o(1) if m n1/2 .
2.1. Sub-Critical Phase 25
As we keep adding edges, trees on more than three vertices start to appear.
Note that isolated vertices, edges and paths of length two are also trees on one,
two and three vertices, respectively. The next two theorems show how long we
have to “wait” until trees with a given number of vertices appear w.h.p.
k−2
Theorem 2.5. Fix k ≥ 3. If m n k−1 , then w.h.p. Gm contains no tree with k
vertices.
k−2
2 3
Proof. Let m = n k−1 /ω and then p = Nm ≈ ωnk/(k−1) ≤ ωnk/(k−1) . Let Xk denote the
number of trees with k vertices in Gn,p . Let T1 , T2 , . . . , TM be an enumeration of
the copies of k-vertex trees in Kn . Let
The probability that a tree T occurs in Gn,p is pe(T ) , where e(T ) is the number of
edges of T . So,
M
E Xk = ∑ P(At ) = M pk−1.
t=1
n k−2
since one can choose a set of k vertices in nk ways and then by
But M = k k
Cayley’s formula choose a tree on these vertices in kk−2 ways. Hence
n k−2 k−1
E Xk = k p . (2.1)
k
Noting also that (see Lemma 27.1(c))
n ne k
≤ ,
k k
we see that
ne k k−1
k−2 3
E Xk ≤ k
k ωnk/(k−1)
3k−1 ek
= → 0,
k2 ω k−1
as n → ∞, seeing as k is fixed.
Thus we see by the first moment method that,
Let us check what happens if the number of edges in Gm is much larger than
k−2
n .
k−1
k−2
Theorem 2.6. Fix k ≥ 3. If m n k−1 , then w.h.p. Gm contains a copy of every
fixed tree with k vertices.
k−2
Proof. Let p = Nm , m = ωn k−1 where ω = o(log n) and fix some tree T with k
vertices. Denote by X̂k the number of isolated copies of T (T -components) in
Gn,p . Let aut(H) denote the number of automorphisms of a graph H. Note that
there are k!/aut(T ) copies of T in the complete graph Kk . To see this choose a
copy of T with vertex set [k]. There are k! ways of mapping the vertices of T to
the vertices of Kk . Each map f induces a copy of T and two maps f1 , f2 induce
the same copy iff f2 f1−1 is an automorphism of T .
So,
n k! k
E X̂k = pk−1 (1 − p)k(n−k)+(2)−k+1 (2.2)
k aut(T )
(2ω)k−1
= (1 + o(1)) → ∞.
aut(T )
k
In (2.2) we have approximated nk ≤ nk! and used the fact that ω = o(log n) in
k
order to show that (1 − p)k(n−k)+(2)−k+1 = 1 − o(1).
Next let T be the set of copies of T in Kn and T[k] be a fixed copy of T on
vertices [k] of Kn . Then, arguing as in (2.3),
2
Notice that the (1 − p)−k factor comes from conditioning on the event
T[k] ⊆i Gn,p which forces the non-existence of fewer than k2 edges.
Hence, by the Second Moment Method,
(E X̂k )2
P(X̂k > 0) ≥ 2
→ 1.
E X̂k 1 + (1 − p)−k E X̂k
2.1. Sub-Critical Phase 27
In the next theorem we show that “on the threshold” for k vertex trees, i.e., if
k−2
m = cn k−1 , where c is a constant, c > 0, the number of tree components of a given
order asymptotically follows the Poisson distribution. This time we will formulate
both the result and its proof in terms of Gm .
k−2
Theorem 2.8. If m = cn k−1 , where c > 0, and T is a fixed tree with k ≥ 3 vertices,
then
P(Gm contains an isolated copy of tree T ) → 1 − e−λ ,
k−1
as n → ∞, where λ = (2c)
aut(T ) .
More precisely, the number of copies of T is asymptotically distributed as the
Poisson distribution with expectation λ .
Proof. Let T1 , T2 , . . . , TM be an enumeration of the copies of some k vertex tree T
in Kn .
Let
Ai = {Ti occurs as a component in Gm }.
Suppose J ⊆ [M] = {1, 2, . . . , M} with |J| = t, where t is fixed. Let AJ = j∈J A j .
T
and so
m2
n−kt
→ 0.
2
Then from Lemma 27.1(f),
m−(k−1)t
n−kt
N 1 − O ktn
2 = (1 + o(1))
m − (k − 1)t (m − (k − 1)t)!
N m−(k−1)t 1 − O mkt
n
= (1 + o(1))
(m − (k − 1)t)!
N m−(k−1)t
= (1 + o(1)) .
(m − (k − 1)t)!
Nm
N
= (1 + o(1)) ,
m m!
and so
m! m (k−1)t
P(AJ ) = (1 + o(1)) N −(k−1)t = (1 + o(1)) .
(m − (k − 1)t)! N
Theorem 2.9. If m = 21 cn, where 0 < c < 1 is a constant, then w.h.p. the order of
the largest component of a random graph Gm is O(log n).
The above theorem follows from the next three lemmas stated and proved in
terms of Gn,p with p = c/n, 0 < c < 1. In fact the first of those three lemmas
covers a little bit more than the case of p = c/n, 0 < c < 1.
Proof. Suppose that there is a pair of cycles that are in the same component.
If such a pair exists then there is minimal pair C1 ,C2 , i.e., either C1 and C2 are
connected by a path (or meet at a vertex) or they form a cycle with a diagonal path
(see Figure 2.1). Then in either case, C1 ∪C2 consists of a path P plus another two
distinct edges, one from each endpoint of P joining it to another vertex in P. The
number of such graphs on k labeled vertices can be bounded by k2 k!.
111
000 111
000 000
111
111
000
000
111 000
111 000
111
000
111
000
111 000
111
000
111 00
11 000
111 000
111
000
111 000
111 000
111 11
00 000
111 111
000
111
000 00
11 000
111
000
111
11
00 000
111 00
11 000
111
00
11
00
11 000
111
00
11 000
111 11
00
00
11
00
11
00
11
000
111 111
000
000
111 00
11 111
000
000
111 111
000
000
111 111
000
000
111 11
00
111
000 000
111 11
00 000
111 000
111 000
111 111
000 00
11
00
11
000
111
000
111 000
111 00
11 000
111 000
111 000
111 000
111 00
11
000
111 000
111 00
11 000
111 000
111 000
111 000
111
000
111
000
111
000
111
111
000 11
00
000
111 00
11
00
11
000
111 00
11 111
000
000
111
111
000
000
111 000
111 000
111
000
111 000
111
000
111
000
111 000
111 000
111 00
11
000
111 111
000 111
000 11
00
000
111
000
111 000
111
000
111 00
11
000
111 000
111 00
11
000
111
111
000
111
000
000
111 000
111
000
111 000
111 111
000
000
111
000
111 000
111 111
000 000
111
000
111 000
111 000
111
000
111
000
111 000
111
000
111 11
00
00
11
00
11
00
11
111
000
000
111
000
111
00
11
11
00 000
111
00
11 000
111 11
00
00
11 00
11
00
11
00
11
000
111 000
111
111
000
111
000
000
111 000
111
000
111 000
111 000
111
000
111
111
000 000
111 111
000 111
000
000
111
000
111 000
111 000
111
000
111
000
111 000
111 000
111
000
111 000
111 000
111
Let X be the number of subgraphs of the above kind (shown in Figure 2.1) in the
random graph Gn,p . By the first moment method (see Lemma 26.2),
n
n 2 k+1
P(X > 0) ≤ E X ≤ ∑ k k!p (2.3)
k=4 k
n
nk 2 ω k+1
1
≤ ∑ k k! k+1 1 − 1/3
k=4 k! n n
Z ∞ 2
x ωx
≤ exp − 1/3 dx
0 n n
2
= 3
ω
= o(1).
We remark for later use that if p = c/n, 0 < c < 1 then (2.3) implies
n
P(X > 0) ≤ ∑ k2ck+1n−1 = O(n−1). (2.4)
k=4
vertices in [k]. This bounds the number C(k, k) of connected graphs on [k] with k
edges. This is off by a factor O(k1/2 ) from the exact formula which is given below
for completeness:
k r
k (r − 1)! k−r−1 π k−1/2
C(k, k) = ∑ rk ≈ k . (2.6)
r=3 r 2 8
2.1. Sub-Critical Phase 31
The remaining factor, other than nk , in (2.5) is the probability that the k edges of
the unicyclic component exist and that there are no other edges on Gn,p incident
with the k chosen vertices.
Noting also that by Lemma 27.1(d),
nk k(k−1)
n
≤ e− 2n .
k k!
So,
n n k c
E ∑ Xk ≤ ∑k ce1−c e 2 = O(1), (2.9)
k=3 k=3
and the Lemma follows for c < 1. If c > 1 then we cannot deduce (2.8) from (2.7).
2
If however k = o(n) then this does not matter, since then ek /n = eo(k) . Now we
show in the proof of Theorem 2.14 below that when c > 1 there is w.h.p. a unique
giant component of size Ω(n) and all other components are of size O(log n). This
giant is not unicyclic. This enables us to complete the proof of this lemma for
c > 1.
After proving the first two lemmas one can easily see that the only remaining
candidate for the largest component of our random graph is an isolated tree.
n kk−2 −c k
E Xk = (1 + o(1)) (ce ) (2.11)
c k!
(1 + o(1)) n
= √ 5/2
(ce1−c )k
c 2π k
(1 + o(1)) n −αk
= √ e , for k = O(log n). (2.12)
c 2π k5/2
Putting k = k− we see that
Thus, by the Chebyshev inequality (see Lemma 26.3), we see that for any ε > 0,
1 2ck2
P (|Xk − E Xk | ≥ ε E Xk ) ≤ 2 + = o(1). (2.15)
ε E Xk ε 2 n
2.1. Sub-Critical Phase 33
If c > 1 then for k ≤ logn n we use cbk e1−bck = e−α−O(1/ log n) and for k > n
log n we use
ck ≥ c/2 and cbk e1−bck ≤ 1 and replace (2.16) by
n n/ log n n
3An 6An 1
∑ E Xk ≤ 5/2 ∑ e−(α+O(1/ log n))k + ∑ 5/2
= o(1).
k=k+ ck+ k=k+ c k=n/ log n k
Finally, applying Lemmas 2.11 and 2.12 we can prove the following useful
identity: Suppose that x = x(c) is given as
(
c c≤1
x = x(c) = −x −c
.
The solution in (0, 1) to xe = ce c>1
Note that xe−x increases continuously as x increases from 0 to 1 and then de-
creases. This justifies the existence and uniqueness of x.
Lemma 2.13. If c > 0, c 6= 1 is a constant, and x = x(c) is defined above, then
1 ∞ kk−1 −c k
∑ k! ce = 1.
x k=1
34 Chapter 2. Evolution
Proof. Let p = nc . Assume first that c < 1 and let X be the total number of vertices
of Gn,p that lie in non-tree components. Let Xk be the number of tree-components
of order k. Then,
n
n= ∑ kXk + X.
k=1
So,
n
n= ∑ k E Xk + E X.
k=1
Now,
n k+ kk−1 k
n = o(n) + ∑ ce−c
c k=1 k!
n ∞ kk−1 k
= o(n) + ∑ ce−c .
c k=1 k!
ce1−c+cβ1 < 1,
using kk−1 /k! < ek , and ce−c < e−1 for c 6= 1 to extend the summation from k0 to
infinity.
36 Chapter 2. Evolution
Putting ε = 1/ log n and using (2.15) we see that the probability that any
Xk , 1 ≤ k ≤ k0 , deviates from its mean by more than 1 ± ε is at most
k0
(log n)2 (log n)4
∑ +O = o(1),
k=1 n1/2−o(1) n
where the n1/2−o(1) term comes from putting ω ≈ k0 /2 in (2.13), which is allowed
by (2.12), (2.14).
Thus, if x = x(c), 0 < x < 1 is the unique solution in (0, 1) of the equation xe−x =
ce−c , then w.h.p.,
k0
n ∞ kk−1 k
∑ kXk ≈ c ∑ k! xe−x
k=1 k=1
nx
= ,
c
by Lemma 2.13.
Now consider k0 < k ≤ β0 log n.
!
β0 log n
n β0 log n 1−c+ck/n k
∑ kXk ≤ ce
c k=k∑
E
k=k0 +1 +1
0
= O n(ce1−c )k0
= O n1/2+o(1) .
!
β0 log n β0 log n
n k−1 k c k c k(n−k)
E ∑ kYk ≤ ∑ k 1−
k=1 k=1 k 2 n n
β0 log n k
1−c+ck/n
≤ ∑ k ce
k=1
= O(1).
2.2. Super-Critical Phase 37
Summarising, we have proved so far that w.h.p. there are approximately nx c ver-
tices on components of order k, where 1 ≤ k ≤ β0 log n and all the remaining giant
components are of size at least β1 n.
We complete the proof by showing the uniqueness of the giant component. Let
log n c1
c1 = c − and p1 = .
n n
Define p2 by
1 − p = (1 − p1 )(1 − p2 )
log n
and note that p2 ≥ n2
. Then, see Section 1.2,
If x1 e−x1 = c1 e−c1 , then x1 ≈ x and so, by our previous analysis, w.h.p., Gn,p1
has no components with number of vertices in the range [β0 log n, β1 n].
Suppose there are components C1 ,C2 , . . . ,Cl with |Ci | > β1 n. Here l ≤ 1/β1 .
Now we add edges of Gn,p2 to Gn,p1 . Then
l 2
(1 − p2 )(β1 n)
P ∃i, j : no Gn,p2 edge joins Ci with C j ≤
2
2
≤ l 2 e−β1 log n
= o(1).
So w.h.p.Gn,p has a unique component with more than β0 log n vertices and it has
≈ 1 − xc n vertices.
We now consider the number of edges in the giant C0 . Now we switch to
G = Gn,m . Suppose that the edges of G are e1 , e2 , . . . , em in random order. We
estimate the probability that e = em = {x, y} is an edge of the giant. Let G1 be the
graph induced by {e1 , e2 , . . . , em−1 }. G1 is distributed as Gn,m−1 and so we know
that w.h.p. G1 has a unique giant C1 and other components are of size O(log n).
So the probability that e is an edge of the giant is o(1) plus the probability that x
or y is a vertex of C1 . Thus,
x x
P e 6∈ C0 | |C1 | ≈ n 1 − = P e ∩C1 = 0/ | |C1 | ≈ n 1 −
c c
|C1 | |C1 | + 1 x 2
= 1− 1− ≈ . (2.18)
n n c
38 Chapter 2. Evolution
Tree-components of order k die out in the reverse order they were born, i.e.,
larger trees are ”swallowed” by the giant earlier than smaller ones.
2.2. Super-Critical Phase 39
Cores
Given a positive integer k, the k-core of a graph G = (V, E) is the largest set S ⊆ V
such that the minimum degree δS in the vertex induced subgraph G[S] is at least
k. This is unique because if δS ≥ k and δT ≥ k then δS∪T ≥ k. Cores were first
discussed by Bollobás [154]. It was shown by Łuczak [636] that for k ≥ 3 either
there is no k-core in Gn,p or one of linear size, w.h.p. The precise size and first
occurrence of k-cores for k ≥ 3 was established in Pittel, Spencer and Wormald
[741]. The 2-core, C2 which is the set of vertices that lie on at least one cycle
behaves differently to the other cores, k ≥ 3. It grows gradually. We will need the
following result in Section 17.2.
Lemma 2.16. Suppose that c > 1 and that x < 1 is the solution to xe−x = ce−c .
Then w.h.p. the 2-core C2 of Gn,p , p = c/n has (1 − x) 1 − xc + o(1) n vertices
2
and 1 − xc + o(1) cn2 edges.
Proof. Fix v ∈ [n]. We estimate P(v ∈ C2 ). Let C1 denote the unique giant compo-
nent of G1 = Gn,p − v. Now G1 is distributed as Gn−1,p and so C1 exists w.h.p. To
be in C2 , either (i) v has two neighbors in C1 or (ii) v has two neighbors in some
other component. Now because all components other than C1 have size O(log n)
w.h.p., we see that
O(log n) c 2
P((ii)) = o(1) + n = o(1).
2 n
Now w.h.p. |C1 | ≈ 1 − xc n and it is independent of the edges incident with v and
so
P((i)) = 1 − P(0 or 1 neighbors in C1 ) =
c |C1 | c |C1 |−1 c
= o(1) + (1 + o(1)) E 1 − 1 − + |C1 | 1 − (2.19)
n n n
= o(1) + 1 − (e−c+x + (c − x)e−c+x )
x
= o(1) + (1 − x) 1 − ,
c
where the last line follows from the fact that e−c+x = xc . Also, one has to be care-
|C |
ful when estimating something like E 1 − nc 1 . For this we note that Jensen’s
inequality implies that
c |C1 | c E |C1 |
E 1− ≥ 1− = e−c+x+o(1) .
n n
On the other hand, if ng = 1 − xc n,
40 Chapter 2. Evolution
c |C1 |
E 1− ≤
n
c |C1 |
E 1− |C1 | ≥ (1 − o(1))ng P (|C1 | ≥ (1 − o(1))ng )
n
+ P (|C1 | ≤ (1 − o(1))ng ) = e−c+x+o(1) .
of |C2 |, we can use the Chebyshev inequality as we did in the proof of Theorem
2.14 to prove concentration for the number of edges in the giant.
To estimate the expected number of edges in C2 , we proceed as in Theorem
2.14 and turn to G = Gn,m and estimate the probability that e1 ⊆ C2 . If G0 = G \ e
and C10 is the giant of G0 then e1 is an edge of C2 iff e1 ⊆ C10 or e1 is contained in
a small component. This latter condition is unlikely. Thus,
0 2
|C1 | x 2
P(e1 ⊆ C2 ) = o(1) + E = o(1) + 1 − .
n c
The estimate for the expectation of the number of edges in the 2-core follows
immediately and one can prove concentration using the Chebyshev inequality.
A natural question arises as to what happens when m/n → 1/2, either from
below or above, as n → ∞. It appears that one can establish, a so called, scaling
window or critical window for the phase transition in which Gm is undergoing a
rapid change in its typical structure. A characteristic feature of this period is that
a random graph can w.h.p. consist of more than one complex component (recall:
there are no complex components in the sub-critical phase and there is a unique
complex component in the super-critical phase).
Erdős and Rényi [332] studied the size of the largest tree in the random graph
Gn,m when m = n/2 and showed that it was likely to be around n2/3 . They called
the transition from O(log n) through Θ(n2/3 ) to Ω(n) the “double jump”. They
did not study the regime m = n/2 + o(n). Bollobás [153] opened the detailed
study of this and Łuczak [634] continued this analysis. He established the precise
size of the “scaling window” by removing a logarithmic factor from Bollobás’s
estimates. The component structure of Gn,m for m = n/2 + o(n) is rather compli-
cated and the proofs are technically challenging. We will begin by stating several
results that give a an idea of the component structure in this range, referring the
reader elsewhere for proofs: Chapter 5 of Janson, Łuczak and Ruciński [509]; Al-
dous [19]; Bollobás [153]; Janson [496]; Janson, Knuth, Łuczak and Pittel [513];
Łuczak [634], [635], [639]; Łuczak, Pittel and Wierman [642]. We will finish
with a proof by Nachmias and Peres that when p = 1/n the largest component is
likely to have size of order n2/3 .
The first theorem is a refinement of Lemma 2.10.
Theorem 2.17. Let m = 2n − s, where s = s(n) ≥ 0.
(a) The probability that Gn,m contains a complex component is at most n2 /4s3 .
(b) If n2/3 s n then w.h.p. the largest component is a tree of size asymptotic
n2 s3
to 2s 2 log n .
The next theorem indicates when the phase in which we may have more than
one complex component “ends”, i.e., when a single giant component emerges.
Theorem 2.18. Let m = n2 + s, where s = s(n) ≥ 0. Then the probability that Gn,m
contains more than one complex component is at most 6n2/9 /s1/3 .
For larger s, the next theorem gives a precise estimate of the size of the largest
component for s n2/3 . For s > 0 we let s̄ > 0 be defined by
2s̄ 2s̄ 2s 2s
1− exp = 1+ exp − .
n n n n
42 Chapter 2. Evolution
n
Theorem 2.19. Let m = 2 + s where s n2/3 . Then with probability at least
1 − 7n2/9 /s1/3 ,
2(s + s̄)n n2/3
L1 − ≤
n + 2s 5
where L1 is the size of the largest component in Gn,m . In addition, the largest
component is complex and all other components are either trees or unicyclic com-
ponents.
To get a feel for this estimate of L1 we remark that
4s2
3
s
s̄ = s − +O 2 .
3n n
The next theorem gives some information about `-components inside the scal-
ing window m = n/2 + O(n2/3 ). An `-component is one that has ` more edges
than vertices. So trees are (-1)-components.
Theorem 2.20. Let m = 2n +O(n2/3 ) and let r` denote the number of `-components
in Gn,m . For every 0 < δ < 1 there exists Cδ such that if n is sufficiently large,
then with probability at least 1 − δ , ∑`≥3 `r` ≤ Cδ and the number of vertices on
complex components is at most Cδ n2/3 .
One of the difficulties in analysing the phase transition stems from the need
to estimate C(k, `), which is the number of connected graphs with vertex set [k]
and ` edges. We need good estimates for use in first moment calculations. We
have seen the values for C(k, k − 1) (Cayley’s formula) and C(k, k), see (2.6).
For ` > 0, things become more tricky. Wright [855], [856], [857] showed that
Ck,k+` ≈ γ` kk+(3`−1)/2 for ` = o(k1/3 ) where the Wright coefficients γ` satisfy an
explicit recurrence and have been related to Brownian motion, see Aldous [19] and
Spencer [810]. In a breakthrough paper, Bender, Canfield and McKay [92] gave
an asymptotic formula valid for all k. Łuczak [633] in a beautiful argument sim-
plified a large part of their argument, see Exercise (4.3.6). Bollobás [155] proved
the useful simple estimate Ck,k+` ≤ c`−`/2 kk+(3`−1)/2 for some absolute constant
c > 0. It is difficult to prove tight statements about Gn,m in the phase transition
window without these estimates. Nevertheless, it is possible to see that the largest
component should be of order n2/3 , using a nice argument from Nachmias and
Peres. They have published a stronger version of this argument in [704].
Theorem 2.21. Let p = n1 and A be a large constant. Let Z be the size of the
largest component in Gn,p . Then
1 2/3
(i) P Z ≤ n = O(A−1 ),
A
2.3. Phase Transition 43
(ii) P Z ≥ An2/3
= O(A−1 ).
Proof. We will prove part (i) of the theorem first. This is a standard application of
the first moment method, see for exampleh Bollobás [155].i Let Xk be the number
1 2/3 2/3
of tree components of order k and let k ∈ A n , An . Then, see also (2.10),
n k−2 k−1 k
E Xk = k p (1 − p)k(n−k)+(2)−k+1 .
k
But
k 2 /2
(1 − p)k(n−k)+(2)−k+1 ≈ (1 − p)kn−k
= exp{(kn − k2 /2) log(1 − p)}
kn − k2 /2
≈ exp − .
n
Hence, by the above and Lemma 27.2,
k3
n
E Xk ≈ √ exp − 2 . (2.20)
2π k5/2 6n
So if
An2/3
X= ∑ Xk ,
1 2/3
An
then
3
1 A e−x /6
Z
EX ≈ √ dx
2π x= A1 x5/2
4
= √ A3/2 + O(A1/2 ).
3 π
Arguing as in Lemma 2.12 we see that
E Xk2 ≤ E Xk + (1 + o(1))(E Xk )2 ,
= 1 − O(A−1 ),
To prove (ii) we first consider a breadth first search (BFS) starting from, say,
vertex x. We construct a sequence of sets S1 = {x}, S2 , . . ., where
[
Si+1 = {v 6∈ S j : ∃w ∈ Si such that (v, w) ∈ E(Gn,p )}.
j≤i
We have
E(|Si+1 | |Si ) ≤ (n − |Si |) 1 − (1 − p)|Si |
≤ (n − |Si |)|Si |p
≤ |Si |.
So
E |Si+1 | ≤ E |Si | ≤ · · · ≤ E |S1 | = 1. (2.21)
We prove next that
4
πk = P(Sk 6= 0)
/ ≤ . (2.22)
k
This is clearly true for k ≤ 4 and we obtain (2.22) by induction from
n−1
n−1 i
πk+1 ≤ ∑ p (1 − p)n−1−i (1 − (1 − πk )i ). (2.23)
i=1 i
To explain the above inequality note that we can couple the construction of S1 , S2 , . . . , Sk
with a (branching) process where T1 = {1} and Tk+1 is obtained from Tk as fol-
lows: each Tk independently spawns Bin(n − 1, p) individuals. Note that |Tk |
stochastically dominates |Sk |. This is because in the BFS process, each w ∈ Sk
gives rise to at most Bin(n − 1, p) new vertices. Inequality (2.23) follows, because
Tk+1 6= 0/ implies that at least one of 1’s children give rise to descendants at level
k. Going back to (2.23) we get
1 1
= πk 1 − πk + o(1) − + o(1) πk
2 6
1
≤ πk 1 − πk .
4
2.4 Exercises
2.4.1 Prove Theorem 2.15.
2.4.2 Show that if p = ω/n where ω = ω(n) → ∞ then w.h.p. Gn,p contains no
unicyclic components. (A component is unicyclic if it contains exactly one
cycle i.e. is a tree plus one extra edge).
2.4.4 Suppose that m = cn/2 where c > 1 is a constant. Let C1 denote the giant
component of Gn,m , assuming that it exists. Suppose that C1 has n0 ≤ n
vertices and m0 ≤ m edges. Let G1 , G2 be two connected graphs with n0
vertices from [n] and m0 edges. Show that
P(C1 = G1 ) = P(C1 = G2 ).
2.4.5 Suppose that Z is the length of the cycle in a randomly chosen connected
n
unicyclic graph on vertex set [n]. Show that, where N = 2 ,
nn−2 (N − n + 1)
EZ = .
C(n, n)
2.4.6 Suppose that c < 1. Show that w.h.p. the length of the longest path in Gn,p ,
log n
p = nc is ≈ log 1/c .
2.4.7 Suppose that c 6= 1 is constant. Show that w.h.p. the number of edges in the
log n
largest component that is a path in Gn,p , p = nc is ≈ c−log c.
2.4. Exercises 47
2.4.8 Let Gn,n,p denote the random bipartite graph derived from the complete bi-
partite graph Kn,n where each edge is included independently with probabil-
ity p. Show that if p = c/n where c > 1 is a constant then w.h.p. Gn,n,p has
a unique giant component of size ≈ 2G(c)n where G(c) is as in Theorem
2.14.
2.4.9 Consider the bipartite random graph Gn,n,p=c/n , with constant c > 1. Define
0 < x < 1 to be the solution to xe−x = ce−c . Prove that w.h.p. the 2-core of
2
Gn,n,p=c/n has ≈ 2(1 − x) 1 − xc n vertices and ≈ c 1 − xc n edges.
2.4.11 Let m = 2n +s, where s = s(n) ≥ 0. Show that if s n2/3 then w.h.p. the ran-
dom graph Gn,m contains exactly one complex component. (A component
C is complex if it contains at least two distinct cycles. In terms of edges, C
is complex iff it contains at last |C| + 1 edges).
2.4.12 Let mk (n) = n(log n + (k − 1) log log n + ω)/(2k), where |ω| → ∞, |ω| =
o(log n). Show that
(
o(1) if ω → −∞
P(Gmk 6⊇ k-vertex-tree-component) = .
1 − o(1) if ω → ∞
2.4.13 Let k ≥ 3 be fixed and let p = nc . Show that if c is sufficiently large, then
w.h.p. the k-core of Gn,p is non-empty.
2.4.14 Let k ≥ 3 be fixed and let p = nc . Show that there exists θ = θ (c, k) > 0
such that w.h.p. all vertex sets S with |S| ≤ θ n contain fewer than k|S|/2
edges. Deduce that w.h.p. either the k-core of Gn,p is empty or it has size at
least θ n.
2.4.15 Suppose that p = nc where c > 1 is a constant. Show that w.h.p. the giant
component of Gn,p is non-planar. (Hint: Assume that c = 1 + ε where ε is
small. Remove a few vertices from the giant so that the girth is large. Now
use Euler’s formula).
2.4.16 Show that if ω = ω(n) → ∞ then w.h.p. Gn,p has at most ω complex com-
ponents.
2.4.17 Suppose that np → ∞ and 3 ≤ k = O(1). Show that Gn,p contains a k-cycle
w.h.p.
48 Chapter 2. Evolution
2.4.18 Suppose that p = c/n where c > 1 is constant and let β = β (c) be the
smallest root of the equation
1 −cβ
(β −1)/β
cβ + (1 − β )ce = log c(1 − β ) .
2
(a) Show that if ω/ log n → ∞ and ω ≤ k ≤ β n then w.h.p. Gn,p contains
no maximal induced tree of size k.
(b) Show that w.h.p. Gn,p contains an induced tree of size (log n)2 .
(c) Deduce that w.h.p. Gn,p contains an induced tree of size at least β n.
2.4.19 Show that if c 6= 1 and xe−x = ce−c where 0 < x < 1 then
(
1 ∞ kk−2 −c k 1 − 2c c < 1.
∑ (ce ) = x x
c 1− 2
c k=1 k! c > 1.
≥k
2.4.20 Let GδN,M denote a graph chosen uniformly at random from the set of graphs
with vertex set [N], M edges and minimum degree at least k. Let Ck denote
the k core of Gn,m (if it exists). Show that conditional on |Ck | = N and
≥k
|E(Ck )| = M that the graph induced by Ck is distributed as GδN,M .
2.4.21 Let p = c/n. Run the Breadth First Search algorithm on Gn,p . Denote by S
the set of vertices that have already been used and uncovered, Q the set of
active vertices in the queue, and T the remaining vertices. Denote by q(s)
the size of Q at the time that |S| = s. Assume that the first vertex to enter Q
belongs to the giant component. Then, finding the expected value of s for
which q(s) = 0 again will give us the size of the giant. Use the Differential
Equations method of Chapter 28 to obtain the size of the giant given in
Theorem 2.14. (This idea was given to us in a private communication by
Sahar Diskin and Michael Krivelevich.)
2.5 Notes
Phase transition
The paper by Łuczak, Pittel and Wierman [642] contains a great deal of informa-
tion about the phase transition. In particular, [642] shows that if m = n/2 + λ n2/3
then the probability that Gn,m is planar tends to a limit p(λ ), where p(λ ) → 0 as
λ → ∞. The landmark paper by Janson, Knuth, Łuczak and Pittel [513] gives the
most detailed analysis to date of the events in the scaling window. Ambroggio and
2.5. Notes 49
Roberts [49], [50] discuss the probability of finding unusually large components
in the scaling window and in critical percolation on random regular graphs. Am-
broggio in [48] discusses the case of unusually small maximal components in the
same models.
Outside of the critical window 2n ± O(n2/3 ) the size of the largest component
is asymptotically determined. Theorem 2.17 describes Gn,m before reaching the
window and on the other hand a unique “giant” component of size ≈ 4s begins to
emerge at around m = 2n + s, for s n2/3 . Ding, Kim, Lubetzky and Peres [296]
give a useful model for the structure of this giant.
Achlioptas processes
Dimitris Achlipotas proposed the following variation on the basic graph process.
Suppose that instead of adding a random edge ei to add to Gi−1 to create Gi ,
one is given a choice of two random edges ei , fi and one chooses one of them
to add. He asked whether it was possible to come up with a choice rule that
would delay the occurrence of some graph property P. As an initial challenge
he asked whether it was possible to delay the production of a giant component
beyond n/2. Bohman and Frieze [137] showed that this was possible by the use
of a simple rule. Since that time this has grown into a large area of research. Kang,
Perkins and Spencer [545] have given a more detailed analysis of the “Bohman-
Frieze” process. Bohman and Kravitz [144] and in greater generality Spencer and
Wormald [812] analyse “bounded size algorithms” in respect of avoiding giant
components. Flaxman, Gamarnik and Sorkin [368] consider how to speed up the
occurrence of a giant component. Riordan and Warnke [763] discuss the speed of
transition at a critical point in an Achlioptas process.
The above papers concern component structure. Krivelevich, Loh and Su-
dakov [595] considered rules for avoiding specific subgraphs. Krivelevich, Lubet-
zky and Sudakov [596] discuss rules for speeding up Hamiltonicity.
Graph Minors
Fountoulakis, Kühn and Osthus [374] show that for every ε > 0 there exists Cε
>
such that if np
2
Cε and p = o(1) then w.h.p. Gn,p contains a complete minor of
n p
size (1 ± ε) log np . This improves earlier results of Bollobás, Catlin and Erdős
[159] and Krivelevich and Sudakov [603]. Ajtai, Komlós and Szemerédi [13]
showed that if np ≥ 1 + ε and np = o(n1/2 ) then w.h.p. Gn,p contains a toplogical
clique of size almost as large as the maximum degree. If we know that Gn,p is non-
planar w.h.p. then it makes sense to determine its thickness. This is the minimum
number of planar graphs whose union is the whole graph. Cooper [243] showed
50 Chapter 2. Evolution
that the thickness of Gn,p is strongly related to its arboricity and is asymptotic to
np/2 for a large range of p.
Chapter 3
Vertex Degrees
In this chapter we study some typical properties of the degree sequence of a ran-
dom graph. We begin by discussing the typical degrees in a sparse random graph
i.e. one with O(n) edges and prove some results on the asymptotic distribution
of degrees. Next we look at the typical values of the minimum and maximum
degrees in dense random graphs. We then describe a simple canonical labelling
algorithm for the graph isomorphism problem on a dense random graph.
E X0 = n(1 − p)n−1 ,
D
distribution. We write Xn → X to say that a random variable Xn converges in
distribution to a random variable X, as n → ∞.
The following theorem shows that the asymptotic distribution of X0 passes
through three phases: it starts in the Normal phase; next when isolated vertices
are close to “dying out”, it moves through a Poisson phase; it finally ends up at
the distribution concentrated at 0.
Theorem 3.1. Let X0 be the random variable counting isolated vertices in a ran-
dom graph Gn,p . Then, as n → ∞,
D
(i) X̃0 = (X0 − E X0 )/(Var X0 )1/2 → N(0, 1),
if n2 p → ∞ and np − log n → −∞,
D
(ii) X0 → Po(e−c ), if np − log n → c, c < ∞,
D
(iii) X0 → 0, if np − log n → ∞.
Proof. For the proof of (i) we refer the reader to Chapter 6 of Janson, Łuczak and
Ruciński [509] (or to [76] and [586]).
To prove (ii) one has to show that if p = p(n) is such that np − log n → c , then
e−ck −e−c
lim P(X0 = k) = e , (3.2)
n→∞ k!
for k = 0, 1, ... . Now,
X0 = ∑ Iv,
v∈V
where (
1 if v is an isolated vertex in Gn,p
Iv =
0 otherwise.
So
E X0 = ∑ E Iv = n(1 − p)n−1
v∈V
= n exp{(n − 1) log(1 − p)}
( )
∞
pk
= n exp −(n − 1) ∑
k=1 k
= n exp −(n − 1)p + O(np2 )
(log n)2
= n exp −(log n + c) + O
n
3.1. Degrees of Sparse Random Graphs 53
≈ e−c . (3.3)
The easiest way to show that (3.2) holds is to apply the Method of Moments
(see Chapter 26). Briefly, since the distribution of the random variable X0 is
uniquely determined by its moments, it is enough to show, that either the kth fac-
torial moment E X0 (X0 − 1) · · · (X0 − k + 1) of X0 , or its binomial moment E Xk0 ,
tend to the respective moments of the Poisson distribution, i.e., to either e−ck or
e−ck /k!. We choose the binomial moments, and so let
(n) X0
Bk = E ,
k
then, for every non-negative integer k,
(n)
Bk = ∑ P(Ivi1 = 1, Ivi2 = 1, . . . , Ivik = 1),
1≤i1 <i2 <···<ik ≤n
n k
= (1 − p)k(n−k)+(2) .
k
Hence
e−ck
(n)
lim Bk = ,
n→∞ k!
and part (ii) of the theorem follows by Theorem 26.11, with λ = e−c .
For part (iii), suppose that np = log n + ω where ω → ∞. We repeat the cal-
culation estimating E X0 and replace ≈ e−c in (3.3) by ≤ (1 + o(1))e−ω → 0 and
apply the first moment method.
From the above theorem we immediately see that if np − log n → c then
−c
lim P(X0 = 0) = e−e . (3.4)
n→∞
We next give a more general result describing the asymptotic distribution of
the number Xd = Xn,d , d ≥ 1 of vertices of any fixed degree d in a random graph.
Recall, that the degree of a vertex in Gn,p has the binomial distribution Bin(n−
1, p). Hence,
n−1 d
E Xd = n p (1 − p)n−1−d . (3.5)
d
Therefore, as n → ∞,
0 if p n−(d+1)/d ,
λ1 if p ≈ cn−(d+1)/d , c < ∞,
∞ if p n−(d+1)/d) but
E Xd → (3.6)
pn − log n − d log log n → −∞,
λ2 if pn − log n − d log log n → c, c < ∞,
0 if pn − log n − d log log n → ∞,
54 Chapter 3. Vertex Degrees
where
cd e−c
λ1 = and λ2 = . (3.7)
d! d!
The asymptotic behavior of the expectation of the random variable Xd suggests
possible asymptotic distributions for Xd , for a given edge probability p.
Proof. The proofs of statements (i) and (v) are straightforward applications of the
first moment method, while the proofs of (ii) and (iv) can be found in Chapter 3
of Bollobás [147] (see also Karoński and Ruciński [553] for estimates of the rate
of convergence). The proof of (iii) can be found in [76].
The next theorem shows the concentration of Xd around its expectation when
in Gn,p the edge probability p = c/n, i.e., when the average vertex degree is c.
Theorem 3.3. Let p = c/n where c is a constant. Let Xd denote the number of
vertices of degree d in Gn,p . Then, for d = O(1), w.h.p.
cd e−c
Xd ≈ n.
d!
Proof. Assume that vertices of Gn,p are labeled 1, 2, . . . , n. We first compute E Xd .
Thus,
E Xd = n P(deg(1) = d) =
n − 1 c d c n−1−d
=n 1−
d n n
3.1. Degrees of Sparse Random Graphs 55
2
nd
d c d c 1
=n 1+O exp −(n − 1 − d) +O 2
d! n n n n
d
c e−c
1
=n 1+O .
d! n
We now compute the second moment. For this we need to estimate
P(deg(1) = deg(2) = d)
c n−1−d 2
c n − 2 c d−1
= 1−
n d −1 n n
c n−2−d 2
c n − 2 c d
+ 1− 1−
n d n n
1
= P(deg(1) = d) P(deg(2) = d) 1 + O .
n
The first line here accounts for the case where {1, 2} is an edge and the second
line deals with the case where it is not.
Thus
Var Xd =
n n
=∑ ∑ [P(deg(i) = d, deg( j) = d) − P(deg(1) = d) P(deg(2) = d)]
i=1 j=1
n
1
≤ ∑ O + E Xd ≤ An,
i6= j=1 n
Theorem 3.4. Let ∆(Gn,p ) (δ (Gn,p )) denotes the maximum (minimum) degree of
vertices of Gn,p .
(i) If p = c/n for some constant c > 0 then w.h.p.
log n
∆(Gn,p ) ≈ .
log log n
56 Chapter 3. Vertex Degrees
log n 1
d log d ≥ · · (log log n − log log log n + o(1))
log log n 1 − 2λ
log n
= (1 + 2λ + O(λ 2 ))(log log n − log log log n + o(1))
log log n
log n
= (log log n + log log log n + o(1)). (3.9)
log log n
Plugging this into (3.8) shows that ∆(Gn,p ) ≤ d− w.h.p.
Now let d = d+ and let Xd be the number of vertices of degree d in Gn,p . Then
n − 1 c d c n−d−1
E(Xd ) = n 1−
d n n
= exp {log n − d log d + O(d)}
log n
= exp log n − (log log n − log log log n + o(1)) + O(d) (3.10)
log log n
→ ∞.
Here (3.10) is obtained by using −λ in place of λ in the argument for (3.9). Now,
for vertices v, w, by the same argument as in the proof of Theorem 3.3, we have
and the Chebyshev inequality implies that Xd > 0 w.h.p. This completes the proof
of (i).
Statement (ii) is an easy consequence of the Chernoff bounds, Corollary 27.7.
Let ε = ω −1/3 . Then
2 np/3 1/3 /3
P(∃v : |deg(v) − np| ≥ εnp) ≤ 2ne−ε = 2n−ω = o(n−1 ).
3.2. Degrees of Dense Random Graphs 57
Now
d r d
d n−1 q n−1
= 1+x =
(n − 1)p (n − 1)p
x2 q
r 3 r
q x pq
= exp x − + O 3/2 p+x
(n − 1)p 2(n − 1)p n n−1
r
pq 2
x q
3
x
= exp x + + O 3/2 ,
n − 1 2(n − 1) n
whereas
d 1− d
n − 1 − d 1− n−1
r
p n−1
= 1−x =
(n − 1)q (n − 1)q
x2 p
r 3 r
p x pq
= exp − x + + O 3/2 q−x
(n − 1)q 2(n − 1)q n n−1
58 Chapter 3. Vertex Degrees
x2 p
r 3
pq x
= exp −x + + O 3/2 ,
n − 1 2(n − 1) n
So
d 1− d
x2
3
d n−1 n−1−d n−1 x
= exp + O 3/2 ,
(n − 1)p (n − 1)q 2(n − 1) n
and lemma follows from (3.11).
The next lemma proves a strengthing of Theorem 3.5.
Lemma 3.7. Let ε = 1/10, and p be constant and q = 1 − p. If
p
d± = (n − 1)p + (1 ± ε) 2(n − 1)pq log n.
then w.h.p.
(i) ∆(Gn,p ) ≤ d+ ,
assuming that p
d ≤ dL = (n − 1)p + (log n)2 (n − 1)pq.
Also, if d > (n − 1)p then
Bd+1 (n − d − 1)p
= <1
Bd (d + 1)q
and so if d ≥ dL ,
E Xd ≤ E XdL ≤ n exp{−Ω(log n)4 }.
It follows that
∆(Gn,p ) ≤ dL w.h.p. (3.13)
Now if Yd = Xd + Xd+1 + · · · + XdL for d = d± then
!2
dL r
n 1 l − (n − 1)p
EYd ≈ ∑ exp − p
l=d 2π pq 2 (n − 1)pq
!2
∞ r
n 1 l − (n − 1)p
≈∑ exp − p (3.14)
l=d 2π pq 2 (n − 1)pq
!2
1 λ − (n − 1)p
r
n
Z ∞
≈ exp − p dλ .
2π pq λ =d 2 (n − 1)pq
and !2
d+ − (n − 1)p
r 1
n
exp − p = n−O(1) .
2π pq 2 (n − 1)pq
p
If d = (n − 1)p + x(n − 1)pq then, from (3.12) we have
!2
1 λ − (n − 1)p
r
n
Z ∞
EYd ≈ exp − p dλ
2π pq λ =d 2 (n − 1)pq
60 Chapter 3. Vertex Degrees
r
n p ∞ Z
2
= (n − 1)pq e−y /2 dy
2π pq y=x
n 1 −x2 /2
≈√ e
2π x
(
≤ n−2ε(1+ε) d = d+
. (3.15)
≥ n2ε(1−ε) d = d−
since
n−2
ˆ = d1 )
P(d(1) d1
= n−1(1
− p)−1
P(deg(1) = d1 ) d1
3.2. Degrees of Dense Random Graphs 61
= 1 + Õ(n−1/2 ).
So, with d = d−
1
P Yd ≤ EYd
2
E(Yd (Yd − 1)) + EYd − (EYd )2
≤
(EYd )2 /4
1
= Õ ε
n
= o(1).
Now
dL
∑ ∑ ˆ = d1 − 1) P(d(2)
P(d(1) ˆ = d2 − 1)
d1 =d− |d2 −d1 |≤10
dL
−1/2 ˆ = d1 − 1) 2 ,
≤ 21(1 + Õ(n )) ∑ P(d(1)
d1 =d−
dL
1
Z ∞
ˆ = d1 − 1) 2 ≈ 2
e−y dy
∑ P(d(1)
d1 =d− 2π pqn y=x
1 ∞Z
−z2 /2
=√ √ e dz
8π pqn z=x 2
1 1 2
≈√ √ n−2(1−ε) ,
8π pqn x 2
62 Chapter 3. Vertex Degrees
ˆ = d1 2 . Thus
We get a similar bound for ∑ddL1 =d− ∑|d2 −d1 |≤10 P(d(1)
2
P(¬(iii)) = o n2−1−2(1−ε)
= o(1).
XL+1 XL+2 · · · Xn
G∼
= H ⇔ vi → wi is an isomorphism.
Proof. Lemma 3.7 implies that Step 1 succeeds w.h.p. We must now show that
w.h.p. Xi 6= X j for all i 6= j > L. There is a slight problem because the edges from
vi , i > L to v j , j ≤ L are conditioned by the fact that the latter vertices are those of
highest degree.
Now fix i, j and let Ĝ = Gn,p \ {vi , v j }. It follows from Lemma 3.7 that if
i, j > L then w.h.p. the L largest degree vertices of Ĝ and Gn,p coincide. So, w.h.p.,
we can compute Xi , X j with respect to Ĝ to create X̂i , X̂ j , which are independent of
the edges incident with vi , v j . It follows that if i, j > L then X̂i = Xi and X̂ j = X j and
this avoids our conditioning problem. Denote by NĜ (v) the set of the neighbors
of vertex v in graph Ĝ. Then
P(Step 2 fails)
≤ o(1) + P(∃vi , v j : NĜ (vi ) ∩ {v1 , . . . , vL } = NĜ (v j ) ∩ {v1 , . . . , vL })
n
≤ o(1) + (p2 + q2 )L
2
= o(1).
Corollary 3.9. If 0 < p < 1 is constant then w.h.p. Gn,p has a unique automor-
phism, i.e. the identity automorphism.
The chromatic index χ 0 (G) of a graph G is the minimum number of colors that
can be used to color the edges of G so that if two edges share a vertex, then they
have a different color. Vizing’s theorem states that
Also, if there is a unique vertex of maximum degree, then χ 0 (G) = ∆(G). So,
it follows from Theorem 3.5 (ii) that, for constant p, w.h.p. we have χ 0 (Gn,p ) =
∆(Gn,p ).
64 Chapter 3. Vertex Degrees
3.3 Exercises
3.3.1 Suppose that m = dn/2 where d is constant. Prove that the number of ver-
k e−d
tices of degree k in Gn,m is asymptotically equal to d k! n for any fixed
positive integer k.
3.3.2 Suppose that c > 1 and that x < 1 is the solution to xe−x = ce−c . Show
that if c= O(1) isfixed then w.h.p. the giant component of Gn,p , p = nc has
k e−c k
≈ c k! 1 − xc n vertices of degree k ≥ 1.
3.3.6 Show that if 0 < p < 1 is constant then w.h.p. the minimum degree δ in
Gn,p satisfies
p p
|δ − (n − 1)q − 2(n − 1)pq log n| ≤ ε 2(n − 1)pq log n,
3.3.9 Use the canonical labelling of Theorem 3.8 to show that w.h.p. Gn,1/2 has
exactly one automprphism, the identity automorphism. (An automorphism
of a graph G = (V, E) is a map ϕ : V → V such that {x, y} ∈ E if and only if
{ϕ(x), ϕ(y)} ∈ E.)
3.4. Notes 65
3.4 Notes
For the more detailed account of the properties of the degree sequence of Gn,p the
reader is referred to Chapter 3 of Bollobás [155].
Erdős and Rényi [331] and [333] were first to study the asymptotic distri-
bution of the number Xd of vertices of degree d in relation with connectivity
of a random graph. Bollobás [151] continued those investigations and provided
detailed study of the distribution of Xd in Gn,p when 0 < lim inf np(n)/ log n ≤
lim sup np(n)/ log n < ∞. Palka [721] determined certain range of the edge prob-
ability p for which the number of vertices of a given degree of a random graph
Gn,p has a Normal distribution. Barbour [73] and Karoński and Ruciński [553]
studied the distribution of Xd using the Stein–Chen approach. A complete answer
to the asymptotic Normality of Xd was given by Barbour, Karoński and Ruciński
[76] (see also Kordecki [586]). Janson [502] extended those results and showed
that random variables counting vertices of given degree are jointly normal, when
p ≈ c/n in Gn,p and m ≈ cn in Gn,m , where c is a constant.
Ivchenko [491] was the first to analyze the asymptotic behavior of the kth-
largest and kth smallest element of the degree sequence of Gn,p . In particular he
analysed the span between the minimum and the maximum degree of sparse Gn,p .
Similar results were obtained independently by Bollobás [149] (see also Palka
[722]). Bollobás [151] answered the question for what values of p(n), Gn,p w.h.p.
has a unique vertex of maximum degree (see Theorem 3.5).
Bollobás [146], for constant p, 0 < p < 1, i.e., when Gn,p is dense, gave √ an es-
timate of the probability that maximum degree does not exceed pn + O( n log n).
A more precise result was proved by Riordan and Selby [760] who showed that
for constant
p p, the probability that the maximum degree ofn Gn,p does not exceed
pn + b np(1 − p), where b is fixed, is equal to (c + o(1)) , for c = c(b) the root
of a certain equation. Surprisingly, c(0) = 0.6102... is greater than 1/2 and c(b)
is independent of p.
McKay and Wormald [672] proved that for a wide range of functions p =
p(n), the distribution of the degree sequence of Gn,p can be approximated by
{(X1 , . . . , Xn )| ∑ Xi is even}, where X1 , . . . , Xn are independent random variables
each having the Binomial distribution Bin(n − 1, p0 ), where p0 is itself a random
variable with a particular truncated normal distribution
66 Chapter 3. Vertex Degrees
Chapter 4
Connectivity
We first establish, rather precisely, the threshold for connectivity. We then view
this property in terms of the graph process and show that w.h.p. the random graph
becomes connected at precisely the time when the last isolated vertex joins the
giant component. This “hitting time” result is the pre-cursor to several similar
results. After this we deal with k-connectivity.
4.1 Connectivity
The first result of this chapter is from Erdős and Rényi [331].
and use Theorem 1.4 to translate to Gm and then use (1.7) and monotonicity for
cn → ±∞.
Let Xk = Xk,n be the number of components with k vertices in Gn,p and con-
sider the complement of the event that Gn,p is connected. Then
n/2
[
= P (Gn,p has a component of order k) =
k=1
n/2
[
P {Xk > 0} .
k=1
n/2
P(X1 > 0) ≤ P(Gn,p is not connected ) ≤ P(X1 > 0) + ∑ P(Xk > 0).
k=2
Now
n/2 n/2 n/2 n/2
n k−2 k−1 k(n−k)
∑ P(Xk > 0) ≤ ∑ E Xk ≤ ∑ k
k p (1 − p) = ∑ uk .
k=2 k=2 k=2 k=2
So
n/2
e−c log n n/2 1+o(1)−k/2
∑ uk ≤ (1 + o(1)) n
+ ∑ n
k=2 k=10
= O no(1)−1 .
It follows that
P(Gn,p is connected ) = P(X1 = 0) + o(1).
4.1. Connectivity 69
But we already know (Theorem 3.1) that for p = (log n + c)/n the number of
isolated vertices in Gn,p has an asymptotically Poisson distribution and therefore,
as in (3.4)
−c
lim P(X1 = 0) = e−e ,
n→∞
and so the theorem follows.
It is possible to tweak the proof of Theorem 4.1 to give a more precise result
stating that a random graph becomes connected exactly at the moment when the
last isolated vertex disappears.
(i) Gm− consists of a giant connected component plus a set V1 of at most 2 log n
isolated vertices,
m− ≤ m∗1 ≤ m∗c ≤ m+ .
E X1 = n(1 − p− )n−1
≈ ne−np−
≈ log n.
Moreover
So,
Var X1 ≤ E X1 + 2(E X1 )2 p− ,
and
Having at least 2 log n isolated vertices is a monotone property and so w.h.p. Gm−
has less then 2 log n isolated vertices.
To show that the rest of Gm is a single connected component we let Xk , 2 ≤
k ≤ n/2 be the number of components with k vertices in G p− . Repeating the
calculations for p− from the proof of Theorem 4.1, we have
!
n/2
o(1)−1
E ∑ Xk = O n .
k=2
Let
E = {∃ component of order 2 ≤ k ≤ n/2}.
4.2. k-connectivity 71
Then
√
P(Gm− ∈ E ) ≤ O( n) P(Gn,p− ∈ E )
= o(1),
4.2 k-connectivity
In this section we show that the threshold for the existence of vertices of degree k
is also the threshold for the k-connectivity of a random graph. Recall that a graph
G is k-connected if the removal of at most k − 1 vertices of G does not disconnect
it. In the light of the previous result it should be expected that a random graph
becomes k-connected as soon as the last vertex of degree k − 1 disappears. This
is true and follows from the results of Erdős and Rényi [333]. Here is a weaker
statement. The stronger statement is left as an exercise, Exercise 4.3.1.
Proof. Let
log n+(k − 1) log log n + c
p= .
n
We will prove that, in Gn,p , with edge probability p above,
(i) the expected number of vertices of degree at most k − 2 is o(1),
e−c
(ii) the expected number of vertices of degree k − 1 is, approximately (k−1)! .
72 Chapter 4. Connectivity
We have
then
1
P ∃S, T, |S| < k, 2 ≤ |T | ≤ (n − |S|) : A (S, T ) = o(1).
2
This implies that if δ (Gn,p ) ≥ k then Gn,p is k-connected and Theorem 4.3 fol-
lows. |T | ≥ 2 because if T = {v} then v has degree less than k.
We can assume that S is minimal and then N(T ) = S and denote s = |S|, t =
|T |. T is connected, and so it contains a tree with t − 1 edges. Also each vertex of
S is incident with an edge from S to T and so there are at least s edges between S
and T . Thus, if p = (1 + o(1)) logn n then
P(∃S, T ) ≤ o(1)+
k−1 (n−s)/2
n n t−2 t−1 st s
∑ ∑ s t t p s p (1 − p)t(n−s−t)
s=1 t=2
k−1 (n−s)/2 s t
ne
≤ p−1 ∑ ∑ · (te) · p · et p ne · p · e−(n−t)p
s=1 t=2 s
k−1 (n−s)/2
≤ p−1 ∑ ∑ At Bs (4.1)
s=1 t=2
where
Now if 2 ≤ t ≤ log n then A = n−1+o(1) and B = O((log n)2 ). On the other hand,
if t > log n then we can use A ≤ n−1/3 and B ≤ n2 to see that the sum in (4.1) is
o(1).
4.3. Exercises 73
4.3 Exercises
4.3.1 Let k = O(1) and let m∗k be the hitting time for minimum degree at least k in
the graph process. Let tk∗ be the hitting time for k-connectivity. Show that
m∗k = tk∗ w.h.p.
4.3.2 Let m = m∗1 be as in Theorem 4.2 and let em = (u, v) where u has degree one.
Let 0 < c < 1 be a positive constant. Show that w.h.p. there is no triangle
containing vertex v.
4.3.3 Let m = m∗1 as in Theorem 4.2 and let em = (u, v) where u has degree one.
Let 0 < c < 1 be a positive constant. Show that w.h.p. the degree of v in Gm
is at least c log n.
4.3.4 Suppose that n log n m ≤ n3/2 and let d = 2m/n. Let Si (v) be the set of
vertices at distance i from vertex v. Show that w.h.p. |Si (v)| ≥ (d/2)i for all
v ∈ [n] and 1 ≤ i ≤ 32 log
log n
d.
4.3.5 Suppose that n log n m ≤ n4/3−ε and let d = m/n. Amend the proof of
the previous question and show that w.h.p. there are at least d/2 internally
vertex disjoint paths of length at most 34 log
log n
d between any pair of vertices in
Gn,m .
4.3.6 Suppose that m n log n and let d = m/n. Suppose that we randomly color
(log n)2
the edges of Gn,m with q colors where q (log d)2
. Show that w.h.p. there
is a rainbow path between every pair of vertices. (A path is rainbow if each
of its edges has a different color).
4.3.7 Let Ck,k+` denote the number of connected graphs with vertex set [k] and
k + ` edges where ` → ∞ with k and ` = o(k). Use the inequality
n k n
Ck,k+` pk+` (1 − p)(2)−k−`+k(n−k) ≤
k k
and a careful choice of p, n to prove (see Łuczak [633]) that
r p !`/2
k3 e + O( `/k)
Ck,k+` ≤ kk+(3`−1)/2 .
` 12`
4.3.8 Let Gn,n,p be the random bipartite graph with vertex bi-partition V = (A, B),
A = [1, n], B = [n + 1, 2n] in which each of the n2 possible edges appears
independently with probability p. Let p = log n+ω
n , where ω → ∞. Show
that w.h.p. Gn,n,p is connected.
74 Chapter 4. Connectivity
4.4 Notes
Disjoint paths
Being k-connected means that we can find disjoint paths between any two sets
of vertices A = {a1 , a2 , . . . , ak } and B = {b1 , b2 , . . . , bk }. In this statement there
is no control over the endpoints of the paths i.e. we cannot specify a path from
ai to bi for i = 1, 2, . . . , k. Specifying the endpoints leads to the notion of linked-
ness. Broder, Frieze, Suen and Upfal [200] proved that when we are above the
connectivity threshold, we can w.h.p. link any two k-sets by edge disjoint paths,
provided some natural restrictions apply. The result is optimal up to constants.
Broder, Frieze, Suen and Upfal [199] considered the case of vertex disjoint paths.
Frieze and Zhao [418] considered the edge disjoint path version in random regular
graphs.
Rainbow Connection
The rainbow connection rc(G) of a connected graph G is the minimum number
of colors needed to color the edges of G so that there is a rainbow path between
everyppair of vertices. Caro, Lev, Roditty, Tuza and Yuster [209] proved that
p = log n/n is the sharp threshold for the property rc(G) ≤ 2. This was sharp-
ened to a hitting time result by Heckel and Riordan [475]. He and Liang [474] fur-
ther studied the rainbow connection of random graphs. Specifically, they obtain a
threshold for the property rc(G) ≤ d where d is constant. Frieze and Tsourakakis
[417] studied the rainbow connection of G = G(n, p) at the connectivity threshold
p = log n+ω
n where ω → ∞ and ω = o(log n). They showed that w.h.p. rc(G) is
asymptotically equal to max {diam(G), Z1 (G)}, where Z1 is the number of ver-
tices of degree one.
Chapter 5
Small Subgraphs
Graph theory is replete with theorems stating conditions for the existence of a
subgraph H in a larger graph G. For example Turán’s theorem [831] states that a
2
graph with n vertices and more than 1 − 1r n2 edges must contain a copy of Kr+1 .
In this chapter we see instead how many random edges are required to have a
particular fixed size subgraph w.h.p. In addition, we will consider the distribution
of the number of copies.
5.1 Thresholds
In this section we will look for a threshold for the appearance of any fixed graph
H, with vH = |V (H)| vertices and eH = |E(H)| edges. The property that a random
graph contains H as a subgraph is clearly monotone increasing. It is also trans-
parent that ”denser” graphs appear in a random graph ”later” than ”sparser” ones.
More precisely, denote by
eH
d(H) = , (5.1)
vH
the density of a graph H. Notice that 2d(H) is the average vertex degree in H.
We begin with the analysis of the asymptotic behavior of the expected number of
copies of H in the random graph Gn,p .
n
Proof. The complete graph on n vertices Kn contains vH aH distinct copies of H,
where aH is the number of copies of H in KvH . Thus
n
E XH = aH peH ,
vH
aH × aut(H) = vH !.
Theorem 5.2. Let H be a fixed graph with eH > 0. Suppose p = o n−1/d(H) .
Then w.h.p. Gn,p contains no copies of H.
Thus
P(XH > 0) ≤ E XH → 0 as n → ∞.
However, as we will see, this is not always enough for Gn,p to contain a copy of a
given graph H w.h.p. To see this, consider the graph H given in Figure 5.1 below.
5.1. Thresholds 77
000
111
000
111
000
111
000
111
000
111
111111
000000
111111 0111111
000
111
1000000
000000
000000 1
111111 0111111
000000
111111
000000
000000
111111 0
1
0000000
111111
111111
000000 1
0111111
1000000
000000
111111
000000 1
111111 0
1000000
111111
000000
111111
000000
111111 0
0000000
111111
000000
111111 1
0111111
1000000
000000 1
111111
111111 0000000
111111
000000
111111
000000 0
1111111
000000
000
111
111111
000000 0111111
1
0
000000
111111
000000000
111
000
111
111111
000000 11
0111111
000000000
111
000
111
000
11111111111111111
00000000000000
0
1 000
111
000
111
1111111
00000001
000
111
1111111 1111111
0
0000000000
111
0000000
000
111
1111111
0000000
1111111
0
1
0000000
1111111
0
1
0000000000
111
00000000
1111111
0000000
1111111 0
0000000
1111111
1
0000000
1111111 0000000
1111111
1
0
0000000
1111111
1
0000000
1111111
00000001
1111111 0
0000000
1111111
0
1111111
0000000
0000000
1111111
1
1111111
0
0000000
1
1111111
0000000
000000010
1111111
0000000
1111111
0000000
1111111 0
0000000
1111111
1
0
1111111
0000000
0000000
1111111
1
0
1111111
0000000
1111111
0000000
1
1111111
0
0000000
1
000
111
000
111
000
111
000
111
000
111 00000000
11111111
00011111111
111 00000000
00000000
11111111 000
111
00000000
11111111 000
111
000
111
00000000 1111111111
11111111
00000000
11111111 000
111
0000000000
00000000
11111111
000
111 000
111
0000000000
1111111111
000
111
00000000
11111111 0000000000
1111111111
000
111
0000000000
1111111111
000
111
000
111
000
111
000
111
Here vH = 6 and eH = 8. Let p = n−5/7 . Now 1/d(H) = 6/8 > 5/7 and so
E XH ≈ cH n6−8×5/7 → ∞.
E XĤ ≤ n4−6×5/7 → 0,
A graph H is balanced if m(H) = d(H). It is strictly balanced if d(H) > d(K) for
all proper subgraphs K ⊂ H.
Now we are ready to determine the threshold for the existence of a copy of
H in Gn,p . Erdős and Rényi [332] proved this result for balanced graphs. The
threshold for any graph H was first found by Bollobás in [147] and an alternative,
deterministic argument to derive the threshold was presented in [552]. A simple
proof, given here, is due to Ruciński and Vince [776].
Observe that random variables Ii and I j are independent iff Hi and H j are edge
disjoint. In this case Cov(Ii , I j ) = 0 and such terms vanish from the above sum-
mation. Therefore we consider only pairs (Hi , H j ) with Hi ∩ H j = K , for some
graph K with eK > 0. So,
2vH −vK 2eH −eK 2eH
Var XH = O ∑ n p −p
K⊆H,e >0
K
= O n2vH p2eH ∑ n−vK p−eK .
K⊆H,eK >0
can be written as
E(XH )k = ∑ P(IHi1 = 1, IHi2 = 1, . . . , IHik = 1)
i1 ,i2 ,...,ik
= Dk + Dk ,
where the summation is taken over all k-element sequences of distinct indices i j
from {1, 2, . . . ,t}, while Dk and Dk denote the partial sums taken over all (ordered)
k tuples of copies of H which are, respectively, pairwise vertex disjoint (Dk ) and
not all pairwise vertex disjoint (Dk ). Now, observe that
Dk = ∑ P(IHi1 = 1) P(IHi2 = 1) · · · P(IHik = 1)
i1 ,i2 ,...,ik
n
= (aH peH )k
vH , vH , . . . , vH
≈ (E XH )k .
fF = fF 0 + fHik − fK = fF 0 − fK < 0,
which completes the induction and implies that d(F) > m(H).
Let CF be the number of sequences Hi1 , Hi2 , . . . , Hik of k distinct copies of H,
such that
k k
Hi j ∼
[ [
V Hi j = {1, 2, . . . , vF } and = F.
j=1 j=1
Proof. The proof is by the Method of Moments (see Lemma 26.7 and Corollary
26.8). Here, instead of the original proof from [775], we shall reproduce its more
compact version, presented in [509].
As in the previous theorem, denote by H1 , H2 , . . . , Ht all copies of H in the com-
plete graph on {1, 2, . . . , n}, where t is given by (5.3). For i = 1, 2, . . . ,t, let
(
1 if Hi ⊆ Gn,p
IHi =
0 otherwise
82 Chapter 5. Small Subgraphs
where the summation in ∑(1) is taken over all graphs L with an even number of
vertices k = 2m and with exactly k/2 edges forming a perfect matching, i.e., k/2
disjoint edges, while ∑(2) takes care of all the remaining graphs L, for k odd or
even.
In the first step, we estimate ∑(1) . One can easily check that in this case
To estimate ∑(2) , first notice that all terms corresponding to graphs L with an
isolated vertex vanish. Indeed, if a vertex j is isolated, it means that IH j − E IH j is
independent from the product ∏i6= j (IHi − E IHi ), and so T (H1 , . . . , Hk ) = 0.
Also notice that, in all the remaining cases, the dependency graph L, for any k
odd or even, has less than k/2 components since each component has to have at
least two and some component has at least three vertices.
Denote the number of components of L by c(L) and without loss of generality,
reorder the vertices of L in such a way that vertices of the first component are
5.2. Asymptotic Distributions 83
In the case of 1/2 < p ≤ 1 we estimate T (H1 , . . . , Hk ) by taking one factor from
each component only, i.e.,
c(L)
|T (H1 , . . . , Hk )| ≤ E ∏ |IHri − E IHri |.
i=1
These factors are independent, and each has the expected value
−1
To estimate ∏ki=1 nv(Fi ) pe(Fi ) , notice that c(L) of the Fi ’s have no edges, so
nv(Fi ) pe(Fi ) = nv(Fi ) ≥ 1, while k − c(L) others have e(Fi ) ≥ 1 and thus
Thus
k k −1
v(H) e(H) c(L) v(Fi ) e(Fi )
n p (1 − p) ∏ n p
i=1
k
c(l)−k c(l)−k
≤ nv(H) pe(H) (1 − p)c(L) ΦH = Θ (E XH )k (1 − p)c(L) ΦH
k/2 c(L)−k/2)
= Θ (Var XH ) ((1 − p)ΦH ) . (5.16)
Finally, merging (5.11) and (5.17) and taking a2n = Var XH in Corollary 26.8 , we
arrive at the thesis.
5.3 Exercises
5.3.1 Draw a graph which is: (a) balanced but not strictly balanced, (b) unbal-
anced.
5.3.2 Are the small graphs listed below, balanced or unbalanced: (a) a tree, (b) a
cycle, (c) a complete graph, (d) a regular graph, (d) the Petersen graph, (e)
a graph composed of a complete graph on 4 vertices and a triangle, sharing
exactly one vertex.
5.3.3 Determine (directly, not from the statement of Theorem 5.3) thresholds p̂
for Gn,p ⊇ G, for graphs listed in exercise (ii). Do the same for the thresh-
olds of G in Gn,m .
5.3.5 Let F be a graph obtained by taking a union of triangles such that not every
pair of them is vertex-disjoint, Show (by induction) that eF > vF .
fF = a vF + b eF ,
86 Chapter 5. Small Subgraphs
5.3.7 Determine (directly, using exercise (v)) when the random variable counting
the number of copies of a triangle in Gn,p has asymptotically the Poisson
distribution.
5.3.8 Let Xe be the number of isolated edges (edge-components) in Gn,p and let
Prove that
(
0 if p n−2 or ω(n) → ∞
P(Xe > 0) →
1 if p n−2 and ω(n) → ∞.
5.3.9 Determine when the random variable Xe defined in exercise (vii) has asymp-
totically the Poisson distribution.
5.3.12 In the proof of Theorem 5.6 show that the condition npm(H) → ∞ is equiva-
lent to ΦH → ∞, as well as that ΦH = Θ(n2 ), when p is a constant.
5.3.13 Prove that the conditions of Theorem 5.6 are also necessary.
5.4 Notes
Distributional Questions
In 1982 Barbour [73] adapted the Stein–Chen technique for obtaining estimates
of the rate of convergence to the Poisson and the normal distribution (see Section
26.3 or [74]) to random graphs. The method was next applied by Karoński and
Ruciński [553] to prove the convergence results for semi-induced graph properties
of random graphs.
Barbour, Karoński and Ruciński [76] used the original Stein’s method for nor-
mal approximation to prove a general central limit theorem for the wide class of
decomposable random variables. Their result is illustrated by a variety of appli-
cations to random graphs. For example, one can deduce from it the asymptotic
distribution of the number of k-vertex tree-components in Gn,p , as well as of the
5.4. Notes 87
number of vertices of fixed degree d in Gn,p (in fact, Theorem 3.2 is a direct
consequence of the last result).
Barbour, Janson, Karoński and Ruciński [75] studied the number Xk of maxi-
mal complete subgraphs (cliques) of a given fixed size k ≥ 2 in the random graph
Gn,p . They show that if the edge probability p = p(n) is such that the E Xk tends to
a finite constant λ as n → ∞, then Xk tends in distribution to the Poisson random
variable with the expectation λ . When its expectation tends to infinity, Xk con-
verges in distribution to a random variable which is normally distributed. Poisson
convergence was proved using Stein–Chen method, while for the proof of the nor-
mal part, different methods for different ranges of p were used such as the first
projection method or martingale limit theorem (for details of these methods see
Chapter 6 of Janson, Łuczak and Ruciński [509]).
Svante Janson in an a sequence of papers [492],[493], [494], [497] (see also
[510]) developed or accommodated various methods to establish asymptotic nor-
mality of various numerical random graph characteristics. In particular, in [493]
he established the normal convergence by higher semi-invariants of sums of de-
pendent random variables with direct applications to random graphs. In [494] he
proved a functional limit theorem for subgraph count statistics in random graphs
(see also [510]).
In 1997 Janson [492] answered the question posed by Paul Erdős: What is the
length Yn of the first cycle appearing in the random graph process Gm ? He proved
that
1 1 j−1 t/2+t 2 /4 √
Z
lim P(Yn = j) = t e 1 − t dt, for every j ≥ 3.
n→∞ 2 0
A careful look reveals that, when ∆H ≥ 2, the minimum in (5.20) is only attained
by ΦH in a tiny range above the existence threshold (when p ≤ n−1/m(H) (log n)aH
for some aH > 0). In 2018, Šileikis and Warnke [805] found counterexample-
graphs (all balanced but not strictly balanced) which violate (5.20) close to the
threshold, and conjectured that (5.20) should hold under the stronger assump-
tion p ≥ n−1/mH +δ .
DeMarco and Kahn [282] proved (5.20) for cliques H = Kk , k = 3, 4, . . . .
Adamczak and Wolff [7] proved a polynomial concentration inequality which con-
k−2
−
firms (5.20) for any cycle H = Ck , k = 3, 4, . . . and p ≥ n 2(k−1) . Moreover, Lubet-
zky and Zhao [631], via a large deviations framework of Chatterjee and Dembo
[213], showed that (5.20) holds for any H and p ≥ n−α for a sufficiently small
constant α > 0. For more recent developments see [237], where it is shown that
one can take α > 1/6∆H .
Chapter 6
Spanning Subgraphs
The previous chapter dealt with the existence of small subgraphs of a fixed size.
In this chapter we concern ourselves with the existence of large subgraphs, most
notably perfect matchings and Hamilton Cycles. The celebrated theorems of Hall
and Tutte give necessary and sufficient conditions for a bipartite and arbitrary
graph respectively to contain a perfect matching. Hall’s theorem in particular can
be used to establish that the threshold for having a perfect matching in a random
bipartite graph can be identified with that of having no isolated vertices.
For general graphs we view a perfect matching as half a Hamilton cycle and
prove thresholds for the existence of perfect matchings and Hamilton cycles in a
similar way.
Having dealt with perfect matchings and Hamilton cycles, we turn our atten-
tion to long paths in sparse random graphs, i.e. in those where we expect a linear
number of edges. We then analyse a simple greedy matching algorithm using
differential equations.
We then consider random subgraphs of some fixed graph G, as opposed to
random subgraphs of Kn . We give sufficient conditions for the existence of long
paths and cycles.
We finally consider the existence of arbitrary spanning subgraphs H where we
bound the maximum degree ∆(H).
random graph.
Bipartite Graphs
Let Gn,n,p be the random bipartite graph with vertex bi-partition V = (A, B), A =
[1, n], B = [n + 1, 2n] in which each of the n2 possible edges appears independently
with probability p. The following theorem was first proved by Erdős and Rényi
[334].
log n+ω
Theorem 6.1. Let ω = ω(n), c > 0 be a constant, and p = n . Then
0
if ω → −∞
−c
lim P(Gn,n,p has a perfect matching) = e−2e if ω → c
n→∞
1 if ω → ∞.
Moreover,
Proof. We will use Hall’s condition for the existence of a perfect matching in a
bipartite graph. It states that a bipartite graph contains a perfect matching if and
only if the following condition is satisfied:
where for a set of vertices S, N(S) denotes the set of neighbors of S. We refer to S
as a witness.
(i) If |S| > |T |+1, we can remove |S|−|T |−1 vertices from |S| – contradiction.
(ii) Suppose ∃w ∈ T such that w has less than 2 neighbors in S. Remove w and
its (unique) neighbor in |S| – contradiction.
n
∀T ⊆ B, |T | ≤ , |N(T )| ≥ |T |. (6.3)
2
This is because if we have a minimal witness S with |S| > n/2 and |N(S)| < |S|
then T = B \ N(S) will violate (6.3).
It follows that
Here e(S : T ) denotes the number of edges between S and T , and e(S : T ) can be
assumed to be at least 2k − 2, because of (b) above.
Suppose now that p = lognn+c for some constant c. Then let Y denote the
number of sets S and T not satisfying the conditions (6.2), (6.3). Then
n/2
n n k(k − 1) 2k−2
EY ≤ 2 ∑ p (1 − p)k(n−k)
k=2 k k−1 2k − 2
n/2
ne k−1 ke(log n + c) 2k−2 −npk(1−k/n)
ne k
≤2∑ e
k=2 k k−1 2n
!k
n/2
eO(1) nk/n (log n)2
≤ ∑n
k=2 n1−1/k
n/2
= ∑ uk .
k=2
Case 1: 2 ≤ k ≤ n3/4 .
So
P(6 ∃ a perfect matching) = P(∃ isolated vertex) + o(1).
Let X0 denote the number of isolated vertices in Gn,n,p . Then
To prove the case for |ω| → ∞ we can use monotonicity and (1.7) and the fact that
−2c −2c
e−e → 0 if c → −∞ and e−e → 1 if c → ∞.
Non-Bipartite Graphs
We now consider Gn,p . We could try to replace Hall’s theorem by Tutte’s theorem.
A proof along these lines was given by Erdős and Rényi [335]. We can however
get away with a simpler approach based on simple expansion properties of Gn,p .
The proof here can be traced back to Bollobás and Frieze [166].
log n+cn
Theorem 6.2. Let ω = ω(n), c > 0 be a constant, and let p = n . Then
0
if cn → −∞
−c
lim P(Gn,p has a perfect matching) = e−e
n→∞
if cn → c
n even
1 if cn → ∞.
Moreover,
Proof. We will for convenience only consider the case where cn = ω → ∞ and
ω = o(log n). If cn → −∞ then there are isolated vertices, w.h.p. and our proof
can easily be modified to handle the case cn → c.
Our combinatorial tool that replaces Tutte’s theorem is the following: We say
that a matching M isolates a vertex v if no edge of M contains v.
For a graph G we let
Let G = (V, E) be a graph without a perfect matching i.e. µ(G) < b|V |/2c. Fix
v ∈ V and suppose that M is a maximum matching that isolates v. Let S0 (v, M) =
{u 6= v : M isolates u}. If u ∈ S0 (v, M) and e = {x, y} ∈ M and f = {u, x} ∈ E
6.1. Perfect Matchings 93
S0 (v, M 0 )
[
A(v, M) =
M0
Proof. Suppose that x ∈ NG (A(v, M)) and that f = {u, x} ∈ E where u ∈ A(v, M).
Now there exists y such that e = {x, y} ∈ M, else x ∈ S0 (M) ⊆ A(v, M). We claim
that y ∈ A(v, M) and this will prove the lemma. Since then, every neighbor of
A(v, M) is the neighbor via an edge of M.
Suppose that y ∈ / A(v, M). Let M 0 be a maximum matching that (i) isolates u
and (ii) is obtainable from M by a sequence of flips. Now e ∈ M 0 because if e has
been flipped out then either x or y is placed in A(v, M). But then we can do another
flip with M 0 , e and the edge f = {u, x}, placing y ∈ A(v, M), contradiction.
We now change notation and write A(v) in place of A(v, M), understanding that
there is some maximum matching that isolates v. Note that if u ∈ A(v) then there is
some maximum matching that isolates u and so A(u) is well-defined. Furthermore,
it always that case that if v is isolated by some maximum matching and u ∈ A(v)
then µ(G + {u, v}) = µ(G) + 1.
Now let
log n + θ log log n + ω
p=
n
where θ ≥ 0 is a fixed integer and ω → ∞ and ω = o(log log n).
We have introduced θ so that we can use some of the following results for the
Hamilton cycle problem.
We write
Gn,p = Gn,p1 ∪ Gn,p2 ,
where
log n + θ log log n + ω/2
p1 =
n
and
ω
1 − p = (1 − p1 )(1 − p2 ) so that p2 ≈ .
2n
Note that Theorem 4.3 implies:
We consider a process where we add the edges of Gn,p2 one at a time to Gn,p1 .
We want to argue that if the current graph does not have a perfect matching then
there is a good chance that adding such an edge {x, y} will increase the size of a
largest matching. This will happen if y ∈ A(x). If we know that w.h.p. every set S
for which |NGn,p1 (S)| < |S| satisfies |S| ≥ αn for some constant α > 0, then
αn
2 − i α2
P(y ∈ A(x)) ≥ n ≥ , (6.6)
2
2
provided i = O(n).
This is because the edges we add will be uniformly random and there will be
αn
at least 2 edges {x, y} where y ∈ A(x). Here given an initial x we can include
edges {x0 , y0 } where x0 ∈ A(x) and y0 ∈ A(x0 ). We have subtracted i to account for
not re-using edges in f1 , f2 , . . . , fi−1 .
In the light of this we now argue that sets S, with |NGn,p1 (S)| < (1 + θ )|S| are
w.h.p. of size Ω(n).
n
Lemma 6.4. Let M = 100(θ + 7). W.h.p. S ⊆ [n], |S| ≤ 2e(θ +5)M implies |N(S)| ≥
(θ + 1)|S|, where N(S) = NGn,p1 (S).
Proof. Let a vertex of graph G1 = Gn,p1 be large if its degree is at least λ = log n
100 ,
and small otherwise. Denote by LARGE and SMALL, the set of large and small
vertices in G1 , respectively.
Proof. If v, w are small and connected by a short path P, then v, w will have few
neighbors outside P and conditional on P existing, v having few neighbors outside
P is independent of w having few neighbors outside P. Hence,
!
(log n)O(1) 2 log n
=O (100e) 100
n
= O(n−3/4 )
= o(1).
λ
λ uk+1
The bound in (6.7) holds since λ ! ≥ e and uk > 100 for k ≤ λ , where
Claim 2. W.h.p. Gn,p1 does not have a 4-cycle containing a small vertex.
Proof.
P(∃ a 4-cycle containing a small vertex )
(log n)/100
4 4 n−4 k
≤ 4n p1 ∑ p1 (1 − p1 )n−4−k
k=0 k
≤ n−3/4 (log n)4
= o(1).
n |S| log n
Claim 3. W.h.p. in Gn,p1 for every S ⊆ [n], |S| ≤ 2eM , e(S) < M .
Proof.
n |S| log n
P ∃|S| ≤ and e(S) ≥
2eM M
n/2eM s
n 2 s log n/M
≤ ∑ p1
s=log n/M
s s log n/M
!log n/M s
n/2eM 1+o(1)
ne Me s
≤ ∑
s=log n/M
s 2n
n/2eM s
s −1+log n/M 1+o(1) log n/M
≤ ∑ · (Me )
s=log n/M
n
= o(1).
96 Chapter 6. Spanning Subgraphs
|N(S)|
≥ |N(S1 )| + |N(S2 )| − |N(S1 ) ∩ S2 | − |N(S2 ) ∩ S1 | − |N(S1 ) ∩ N(S2 )|
≥ |N(S1 )| + |N(S2 )| − |S2 | − |N(S2 ) ∩ S1 | − |N(S1 ) ∩ N(S2 )|.
But Claim 1 and Claim 2 and minimum degree at least θ + 1 imply that
|N(S1 )| ≥ (θ + 1)|S1 |, |N(S2 ) ∩ S1 | ≤ min{|S1 |, |S2 |}, |N(S1 ) ∩ N(S2 )| ≤ |S2 |.
So, from this and Claim 4 we obtain
|N(S)| ≥ (θ + 1)|S1 | + (θ + 4)|S2 | − 3|S2 | = (θ + 1)|S|.
We now go back to the proof of Theorem 6.2 for the case c = ω → ∞. Let
the edges of Gn,p2 be { f1 , f2 , . . . , fs } in random order, where s ≈ ωn/4. Let G0 =
Gn,p1 and Gi = Gn,p1 + { f1 , f2 , . . . , fi } for i ≥ 1. It follows from Lemmas 6.3 and
6.4 that with µ(G) as in (6.4), and if µ(Gi ) < n/2 then, assuming Gn,p1 has the
1
expansion claimed in Lemma 6.4, with θ = 0 and α = 10eM ,
α2
P(µ(Gi+1 ) ≥ µ(Gi ) + 1 | f1 , f2 , . . . , fi ) ≥ , (6.8)
2
see (6.6).
It follows that
Moreover,
Proof. We will first give a proof of the first statement under the assumption that
cn = ω → ∞ where ω = o(log log n). The proof of the second statement is post-
poned to Section 6.3. Under this assumption, we have δ (Gn,p ) ≥ 2 w.h.p., see
Theorem 4.3. The result for larger p follows by monotonicity.
We now set up the main tool, viz. Pósa’s Lemma. Let P be a path with end
points a, b, as in Figure 6.1. Suppose that b does not have a neighbor outside of P.
P
111
000
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
00
11
00
11
00
11
y00
11
00
11
00
11
000
111
000
111 000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
0000
1111
0000
1111 000
1111111
0000 000
111
000
111 0000
1111
000
111 0000
1111000
111
000
111 0000
1111
0000
1111000
111
000
1110000
1111
0000
1111000
111
0000
1111 111
0001111
1110000 111
1111 000 1111
111
0000 1111
0001111
0000111
000 0000
1111000
1110000
1111111
000
000
0000 111
1111 0000000
0000
1111
1111
111
0000
000
000 1111
111 0000
000
111 0000
0000
11110001111
111 0000111
1111 0000111
0001111
1111111000
000
111
0000
1111
0000
1111 0001111
111 000
111
0000 111
1111 000 0000
1111
0001111
111 000
111
0000111
1111000 0000
0000
1111000
000
1110000
0000
1111000
111
000
111
0000 111
1111 0000000
0000
1111 0000
1111
000
111
000 1111
111 0000
000
111 0000
0000
11110001111
111 0000111
1111 0000111
0001111
1111111000
000
111
0000
1111
1111 000
1110000
1111 000
111 0000
1111
000
111 0000
1111000
111 00000000000000
111
0000
0000
1111 0001111
111 111
000
0000 111
1111 000 0000
1111
0001111
111 111
000
0000111
1111000 1111
0000
0000
1111111
000
000
1111111
0000
0000
1111000
111
000
111
0000 111
1111 0000000
0000
1111 0000
1111
000
111
000 1111
111 0000
000
111 0000
0000
11110001111
111 0000111
1111 0000111
0001111
1111111000
000
111
0000
1111
000
111
0000
1111 000
111
000
111 000
111
0000 111
1111 000
111
000 0000
1111
000
111
000
111 000
111
0000111
1111 0000
000
111
000 11110000000
00
11 000
111
00
11
000
111
1111 000
1110000
1111
000
111
0000 111 000
111
111
000 0000
1111
000
111 0000
1111
000
111 0000
000
111 000
1110000
1111
0000111
00
11 000
00
11
000
111 000
000
111 000
1110000
1111
000
111 0000111
1111
000
111 000 1111
0000111
000
111
1111
00000001111
00
11 000
111
00
11
000
111 000
111 000
111 000
111 000
111 00
11 00
11
000
111
a 000
111 000
111 000
111
x000
111 00
11 00
11 b
Notice that the P0 below in Figure 6.2 is a path of the same length as P, ob-
tained by a rotation with vertex a as the fixed endpoint. To be precise, suppose
that P = (a, . . . , x, y, y0 , . . . , b0 , b) and {b, x} is an edge where x is an interior vertex
of P. The path P0 = (a, . . . , x, b, b0 , . . . , y0 , y) is said to be obtained from P by a
rotation.
Now let END = END(P) denote the set of vertices v such that there exists a
path Pv from a to v such that Pv is obtained from P by a sequence of rotations with
vertex a fixed as in Figure 6.3.
98 Chapter 6. Spanning Subgraphs
P’
111
000
000
111
000
111
000
111
000
111
000
111
000
111
000
111
000
111
111
000
000
111
000
111
y 00
11
00
11
00
11
00
11
00
11
00
11
000
111
000111
111 000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
1111
0000 0001111
0000 111
000 1111
111
0000
000 111
000 1111
0000111
0001111
0000
1111
0000 111
0000
1111 0000000
1111 111
000 1111
000
111 0000
000
111 111
000
111
1111
0001111
0000
111
0000111
0000000111
1111
0001111
0000
000
000
111
0000
1111 000
111
1110000
1111 000
111 0000
1111
000
111 000
111 0000
1111000
1110000
1111000
111
0000
1111 111
000
1111
0001111
0000 111
0000 000 1111
111
0000
000
1111
111
0000
000 000
111 0000
1111000
1110000
1111111
000
0000 111
1111
1111 0000000
1111 000 1111
111 0000
000
111 0001111
111 0000111
11111110000111
0001111
1111000
000
111
0000
1111
0000 0001111
111 111
000
0000 111
1111 000 0000
1111
000
111 111
000
111
000 0000
1111
0000000
111
0000000
1111
0000000
111
1111 000
111
0000 1110000 0000
1111
000
111
000 1111
111 0001111
111 0000111
1111 0000111
0001111
1111111000
0000
1111 000
111
000
1111
0000
1111
0000 000
111 111
0000
000
1111
111
0000
000 000
111 00000000000111
000
111
000
0000
1111
1111 111
0001111 000
111
0000 111
1111 1111
111
0000
000 000
111 1111
0000000
1110000
1111111
000
0000
000
111
1111 000
1110000
000
111
0000 111 000
000
111
111
000 0000
1111
000
111
000
111 111
000 1111
0000
000
111
111
000 1111111
0001111
0000
0000111
00
11
111
0000111
0001111000
00
11
000
111
0000
1111 000
1110000
1111
000
111 000
111
000
111 0000
1111
000
111
000
111 000
111
000
111 0000
1111 00
11
0000000
1111000
111
00
11
000
111 000
000
111 000
1111111
111
0000
000
000
111 000
111
0000
1111 00
11 111
000
00
11
000
111 000
111 000
111 000
111 000
111 00
11 00
11
000
111
a 000
111 000
111 000
111
x 000
111 00
11 00
11 b
Here the set END consists of all the white vertices on the path drawn below in
Figure 6.4.
Proof. Suppose to the contrary that x, y are the neighbors of v on P and that v, x, y 6∈
END and that v is adjacent to w ∈ END. Consider the path Pw . Let {r,t} be the
neighbors of v on Pw . Now {r,t} = {x, y} because if a rotation deleted {v, y} say
then v or y becomes an endpoint. But then after a further rotation from Pw we see
that x ∈ END or y ∈ END.
6.2. Hamilton Cycles 99
000
111 111
000 000
111 00
11 00
11
000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
1111
0000
0000
1111 1111
0000 000
111
000
111 1111
111
0000
000 1111
0000000
111
000
1110000
1111
0000
1111000
111
000
1110000
1111
0000
1111111
000
1111
0000 0000 111
1111
0000
1111
1111
111
0000
0001111
000 1111
0000
000
111
1111
0000111
0000 1111
0001111111
00001111111
0001111111
000
0000111
000
1111
0000 0000
1111 111
000 0000
1111
000
111 0000
1111111
00000000000000000
111
0000
1111
0000
1111 1111 000
111
0000 111
000 1111
111
0000 1111
0001111 000
111
0000111
0000000
1111
0000
1111000
111
000
1110000
1111
0000
1111111
000
0000
1111 0000
1111
0000
1111
1111
111
0000
000
000 1111
111 0000
000
111 0000
0000
11110001111
1110000111
1111 0000111
0001111
1111111000
000
111
1111
0000
1111 0000
1111 111
000 0000
1111
000
111 0000
1111111
00000000000000000
111
0000
0000
1111
111
000
0000 111
1111 000 0000
1111
0001111
111 111
000
0000111
1111000
1111
0000
0000
1111
111
000
000
111
1111
0000
0000
1111000
111
0000
1111 1111
0000 1111
111
0000
000
000 1111
111 00000001111
1110000111
1111 0000111
0001111
1111111000
0000
1111 0000
1111 000
111
0000 111
1111
111
0000
000
0000
1111
000
111
1111
0000000
111
0000111
1111 00000000000111
000
000
111
000
111
1111
0000 0000
1111 000
111
000 0000
1111 000
111
000
111 0000
1111 000
111
0001111
0000 00
11
111
0001111
0000
000
111
1111
0000
000
111 000
111
111
000
000
1110000
1111 000
111
000
111 1111
000
111 000
111
0000111
0001111
000
111
0000
11110000000111
00
11
00001111111
00
11
000
000
111
000
111 000
111 000
111 000
111 00
11
000
111
a 000
111 000
111 000
111 00
11 b
111
000 000
111 000
111
r 000
111 t 00
11 00
11
000
111
000
111 000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
000
111
000111
111 000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
1111
0000 0001111
0000 111
000 1111
111
0000
000 1111
0000111
000 1111
0000111
0001111
0000
0000 111
1111
0000
1111 0000000
1111 000 1111
111
000
111 111
0000
000 1111
00000001111
111
000
111 0000111
1111
00000000000111
0001111
1111111
0000
000
111
000
0000
1111 000
1110000
1111
0001111
111 000
111
0000 111
1111 0000
1111
000
111
0000
1111 0000
1111
0001111
111 000
111
0000111
1111 0000
1111000
1110000
1111000
111
000
111
0000
1111 000
111
0000 111
1111 0000 000
111 0000
1111
000
111
000 1111 0000000 0000
1111
0001111
111 000
111
0000111
1111 0000
1111
0000111
0001111
1111111000
0000
1111 000
000
1110000
1111
0000
1111 000
111 0000
000
111
0000
1111
000
111 0000
1111
0000
1111000
111 00000000000000
111
000
111
0000
1111
1111 0001111
111 000
111
0000 111
1111 0000
1111
0001111
111 000
111
0000111
1111 0000
1111000
1110000
1111000
111
0000
1111 000
111
0000 0000000 000
111 0000
1111
000
111
000 0000 0000000
111 1111
0000
1111
0001111
111
000
111
0000111
1111
0000
0000111
1111
0001111000
1111
0000 1111111
0000
1111111 111
000 1111
111
000 1111
0000111
000 00000000000111
000
0000
1111 000
111
0000000 111
0000
1111 000 1111
1111111
0000
000
1111
111
0000
000
1111111
0000
0000000 0000
1111000
1110000
1111111
000
000
111
000
111
0000
1111
000
111
0000 111
1111 0000000
1111
000
111 000
111
000
111
000
111
000
111 0000
1111 000
111
000
111 0000
1111
000
111 000
111
000
111 0000111
1111
000
111
000
111 0000
1111000
1110000111
00
11
1111
00
11
0000000
1111
000
00
11
000
111
00
11
000
111 000
111
000
111 000
1110000
1111
000
111 0000 111
1111
000
111 000
0000
1111 00
11 000
111
00
11
000
111
000
111 000
111
000
111 000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
a v w
Corollary 6.7.
|N(END)| < 2|END|.
1
|END| ≥ αn where α = . (6.9)
12eM
We now consider the following algorithm that searches for a Hamilton cycle
in a connected graph G. The probability p1 is above the connectivity threshold
and so Gn,p1 is connected w.h.p. Our algorithm will proceed in stages. At the
beginning of Stage k we will have a path of length k in G and we will try to grow
it by one vertex in order to reach Stage k + 1. In Stage n − 1, our aim is simply
to create a Hamilton cycle, given a Hamilton path. We start the whole procedure
with an arbitrary path of G.
Algorithm Pósa:
(a) Let P be our path at the beginning of Stage k. Let its endpoints be x0 , y0 . If x0
or y0 have neighbors outside P then we can simply extend P to include one of
these neighbors and move to stage k + 1.
100 Chapter 6. Spanning Subgraphs
(b) Failing this, we do a sequence of rotations with x0 as the fixed vertex until one
of two things happens: (i) We produce a path Q with an endpoint y that has a
neighbor outside of Q. In this case we extend Q and proceed to stage k + 1.
(ii) No sequence of rotations leads to Case (i). In this case let END denote
the set of endpoints of the paths produced. If y ∈ END then Py denotes a path
with endpoints x0 , y that is obtained from P by a sequence of rotations.
(c) If we are in Case (bii) then for each y ∈ END we let END(y) denote the set
of vertices z such that there exists a longest path Qz from y to z such that Qz is
obtained from Py by a sequence of rotations with vertex y fixed. Repeating the
argument above in (b) for each y ∈ END, we either extend a path and begin
Stage k + 1 or we go to (d).
(d) Suppose now that we do not reach Stage k + 1 by an extension and that we
have constructed the sets END and END(y) for all y ∈ END. Suppose that
G contains an edge (y, z) where z ∈ END(y). Such an edge would imply
the existence of a cycle C = (z, Qy , z). If this is not a Hamilton cycle then
connectivity implies that there exist u ∈ C and v ∈ / C such that u, v are joined
by an edge. Let w be a neighbor of u on C and let P0 be the path obtained from
C by deleting the edge (u, w). This creates a path of length k + 1 viz. the path
w, P0 , v, and we can move to Stage k + 1.
α2
P(λ (Gi+1 ) ≥ λ (Gi ) + 1 | f1 , f2 , . . . , fi ) ≥ , (6.10)
2
Proof. We prove this theorem by analysing simple properties of Depth First Search
(DFS). This is a well known algorithm for exploring the vertices of a component
of a graph. We can describe the progress of this algorithm using three sets: U is
the set of unexplored vertices that have not yet been reached by the search. D is
the set of dead vertices. These have been fully explored and no longer take part in
the process. A = {a1 , a2 , . . . , ar } is the set of active vertices and they form a path
from a1 to ar . We start the algorithm by choosing a vertex v from which to start
the process. Then we let
We now describe how these sets change during one step of the algorithm.
Step (a) If there is an edge {ar , w} for some w ∈ U then we choose one such w
and extend the path defined by A to include w.
D ← D ∪ {ar }; A ← A \ {ar }; r ← r − 1.
102 Chapter 6. Spanning Subgraphs
• A step of the algorithm increases |D| by one or decreases |U| by one and so
at some stage we must have |D| = |U| = s for some positive integer s.
Thus at some stage we have two disjoint sets D,U of size s with no edges between
them and a path of length |A| − 1 = n − 2s − 1. This plus the following claim
6 log c
implies that Gn,p has a path P of length at least 1 − c n w.h.p. Note that if c
is large then
3 log c 2 e
α> implies c > log .
c α α
Claim 5. Let 0 < α < 1 be a positive constant. If p = c/n and c > α2 log αe then
w.h.p. in Gn,p , every pair of disjoint sets S1 , S2 of size at least αn − 1 are joined
by at least one edge.
Proof. The probability that there exist sets S1 , S2 of size (at least) αn − 1 with no
joining edge is at most
2 !αn−1
e2+o(1) −cα
n (αn−1)2
(1 − p) ≤ e = o(1).
αn − 1 α2
To complete the proof of the theorem, we apply the above lemma to the ver-
tices S1 , S2 on the two sub-paths P1 , P2 of length 3 log c
c n at each end of P. There
will w.h.p. be an edge joining S1 , S2 , creating the cycle of the claimed length.
Krivelevich and Sudakov [604] used DFS to give simple proofs of good bounds
on the size of the largest component in Gn,p for p = 1+ε n where ε is a small con-
stant. Exercises 6.7.19, 6.7.20 and 6.7.21 elaborate on their results.
6.4. Greedy Matching Algorithm 103
begin
M ← 0;/
while E(G) 6= 0/ do
begin
104 Chapter 6. Spanning Subgraphs
(G \ {x, y} is the graph obtained from G by deleting the vertices x, y and all
incident edges.)
(B)
We will study this algorithm in the context of the pseudo-graph model Gn,m of
Section 1.3 and apply (1.17) to bring the results back to Gn,m . We will argue next
that if at some stage G has ν vertices and µ edges then G is equally likely to be
any pseudo-graph with these parameters.
We will use the method of deferred decisions, a term coined in Knuth, Mot-
wani and Pittel [573]. In this scenario, we do not expose the edges of the pseudo-
graph until we actually need to. So, as a thought experiment, think that initially
there are m boxes, each containing a uniformly random ordered pair of distinct
integers x, y from [n]. Until the box is opened, the contents are unknown except
for their distribution. Observe that opening box A and observing its contents tells
us nothing more about the contents of box B. This would not be the case if as in
Gn,m we insisted that no two boxes had the same contents.
Remark 6.9. A step of GREEDY involves choosing the first unopened box at
random to expose its contents x, y.
After this, the contents of the remaining boxes will of course remain uniformly
random. The algorithm will then ask for each box with x or y to be opened. Other
boxes will remain unopened and all we will learn is that their contents do not
contain x or y and so they are still uniform over the remaining possible edges.
Now let X(t) = (ν(t), µ(t)),t = 1, 2, . . . , denote the number of vertices and
edges in the graph at the end of the tth iteration of GREEDY. Also, let Gt =
(Vt , Et ) = G at this point and let Gt0 = (Vt , Et \ e) where e is a uniform random
(B)
edge of Et . Thus ν(1) = n, µ(1) = m and G1 = Gn,m . Now ν(t + 1) = ν(t) − 2
and so ν(t) = n − 2t + 2. Let dt (·) denote degree in Gt0 and let θt (x, y) denote the
number of copies of the edge {x, y} in Gt , excluding e. Then we have
E(µ(t + 1)) = E(µ(t)) − E(dt (x)) − E(dt (y)) + 1 + E(θt (x, y)).
1 ν(t)
1
= ∑ dt (i)2 + O .
µ(t) i=1 µ(t)
!
1 ν(t) ν(t) µ(t) 2 µ(t) 2 k 2 µ(t)−k
2
E ∑ dt (i) µ(t) = µ(t) ∑ k k 1−
µ(t) i=1 k=0 ν(t) ν(t)
2 2µ(t)
= 2 1− + .
ν(t) ν(t)
So,
4 E(µ(t)) 1
E(µ(t + 1)) = E(µ(t)) − −1+O . (6.12)
n − 2t n − 2t
Here we use Remark 6.9 to argue that E θt (x, y)) = O(1/(n − 2t)).
106 Chapter 6. Spanning Subgraphs
This suggests that w.h.p. µ(t) ≈ nz(t/n) where z(0) = c and z(τ) is the solution
to the differential equation
dz 4z(τ)
=− − 1.
dτ 1 − 2τ
This is easy to solve and gives
1 1 − 2τ
z(τ) = c + (1 − 2τ)2 − .
2 2
c
The smallest root of z(τ) = 0 is τ = 2c+1 . This suggests the following theorem.
Theorem 6.11. W.h.p., running GREEDY on Gn,cn finds a matching of size c+o(1)
2c+1 n.
(B)
Proof. We will replace Gn,m by Gn,m and consider the random sequence µ(t),
t = 1, 2, . . .. The number of edges in the matching found by GREEDY equals one
less than the first value of t for which µ(t) = 0. We show that w.h.p. µ(t) > 0 if
and only if t ≤ c+o(1)
2c+1 n. We will use Theorem 28.1 of Chapter 28.
In our set up for the theorem we let
4x
f (τ, x) = − − 1.
1 − 2τ
1 c 1
D = (τ, x) : − < t < TD = ,0 < x < .
n 2c + 1 2
We let X(t) = µ(t) for the statement of the theorem. Then we have to check the
conditions:
(P1) |µ(t)| ≤ cn, ∀t < TD = TD n.
| f (t, x) − f (t 0 , x0 )|
4x 4x0
= −
1 − 2t 1 − 2t 0
6.5. Random Subgraphs of Graphs with Large Minimum Degree 107
Now let β = n1/5 and λ = n−1/20 and σ = T D − 10λ and apply the theorem.
This shows that w.h.p. µ(t) = nz(t/n) + O(n19/20 ) for t ≤ σ n.
The result in Theorem 6.11 is taken from Dyer, Frieze and Pittel [324], where a
central limit theorem is proven for the size of the matching produced by GREEDY.
The use of differential equations to approximate the trajectory of a stochastic
process is quite natural and is often very useful. It is however not always best
practise to try and use an “off the shelf” theorem like Theorem 28.1 in order to
get a best result. It is hard to design a general theorem that can deal optimally
with terms that are o(n).
Proof. We will assume that G has n vertices. We let T denote the forest produced
by depth first search. We also let D,U, A be as in the proof of Theorem 6.8. Let
v be a vertex of the rooted forest T . There is a unique vertical path from v to the
root of its component. We write A (v) for the set of ancestors of v, i.e., vertices
(excluding v) on this path. We write D(v) for the set of descendants of v, again
excluding v. Thus w ∈ D(v) if and only if v ∈ A (w). The distance d(u, v) between
two vertices u and v on a common vertical path is just their graph distance along
this path. We write Ai (v) and Di (v) for the set of ancestors/descendants of v
at distance exactly i, and A≤i (v), D≤i (v) for those at distance at most i. By the
108 Chapter 6. Spanning Subgraphs
depth of a vertex we mean its distance from the root. The height of a vertex v
is max {i : Di (v) 6= 0}.
/ Let R denote the set of edges of G that are not tested for
inclusion in G p during the exploration.
Lemma 6.13. Every edge e of R joins two vertices on some vertical path in T .
Proof. Let e = {u, v} and suppose that u is placed in D before v. When u is placed
in D, v cannot be in U, else {u, v} would have been tested. Also, v cannot be in D
by our choice of u. Therefore at this time v ∈ A and there is a vertical path from v
to u.
Lemma 6.14. With high probability, at most 2n/p = o(kn) edges are tested during
the depth first search exploration.
Proof. Each time an edge is tested, the test succeeds (the edge is found to be
present) with probability p. The Chernoff bound implies that the probability that
more than 2n/p tests are made but fewer than n succeed is o(1). But every suc-
cessful test contributes an edge to the forest T , so w.h.p. at most n tests are suc-
cessful.
From now on let us fix an arbitrary (small) constant 0 < ε < 1/10. We call a
vertex v full if it is incident with at least (1 − ε)k edges in R.
Lemma 6.15. With high probability, all but o(n) vertices of Tk are full.
Proof. For each rich vertex v, let P(v) be a set of dεke descendants of v, obtained
by choosing vertices of D(v) one-by-one starting with those furthest from v. For
every w ∈ P(v) we have D(w) ⊆ P(v), so |D(w)| < εk, i.e., w is poor. Consider
the set S1 of ordered pairs (v, w) with v rich and w ∈ P(v). Each of the n − o(n)
rich vertices appears in at least εk pairs, so |S1 | ≥ (1 − o(1))εkn.
For any vertex w we have |A≤i (w)| ≤ i, since there is only one ancestor at
each distance, until we hit the root. Since (v, w) ∈ S1 implies that w is poor and
v ∈ A (w), and there are only o(n) poor vertices, at most o(Ckn) = o(kn) pairs
(v, w) ∈ S1 satisfy d(v, w) ≤ Ck. Thus S10 = {(v, w) ∈ S1 : d(v, w) > Ck} satisfies
6.5. Random Subgraphs of Graphs with Large Minimum Degree 109
|S10 | ≥ (1 − o(1))εkn. Since each vertex v is the first vertex of at most dεke ≈ εk
pairs in S1 ⊇ S10 , it follows that n − o(n) vertices v appear in pairs (v, w) ∈ S10 .
Since any such v has height at least Ck, the proof is complete.
Let us call a vertex v light if |D ≤(1−5ε)k (v)| ≤ (1 − 4ε)k, and heavy otherwise.
Let H denote the set of heavy vertices in T .
Lemma 6.17. Suppose that T = Tk contains o(n) poor vertices, and let X ⊆ V (T )
with |X| = o(n). Then, for k large enough, T contains a vertical path P of length
at least ε −2 k containing at most ε 2 k vertices in X ∪ H.
Proof. Let S2 be the set of pairs (u, v) where u is an ancestor of v and 0 < d(u, v) ≤
(1 − 5ε)k. Since a vertex has at most one ancestor at any given distance, we have
|S2 | ≤ (1 − 5ε)kn. On the other hand, by Lemma 6.16 all but o(n) vertices u are
at height at least k and so appear in at least (1 − 5ε)k pairs (u, v) ∈ S2 . It follows
that only o(n) vertices u are in more than (1 − 4ε)k such pairs, i.e., |H| = o(n).
Let S3 denote the set of pairs (u, v) where v ∈ X ∪ H, u is an ancestor of v, and
d(u, v) ≤ ε −2 k. Since a given v can only appear in ε −2 k pairs (u, v) ∈ S3 , we see
that |S3 | ≤ ε −2 k|X ∪ H| = o(kn). Hence only o(n) vertices u appear in more than
ε 2 k pairs (u, v) ∈ S3 .
By Lemma 6.16, all but o(n) vertices are at height at least ε −2 k. Let u be such
a vertex appearing in at most ε 2 k pairs (u, v) ∈ S3 , and let P be the vertical path
from u to some v ∈ D ε −2 k (u). Then P has the required properties.
Proof of Theorem 6.12
Fix ε > 0. It suffices to show that w.h.p. G p contains a cycle of length at least
(1 − 5ε)k, say. Explore G p by depth-first search as described above. We condition
on the result of the exploration, noting that the edges of R are still present inde-
pendently with probability p. By Lemma 6.13, {u, v} ∈ R implies that u is either
an ancestor or a descendant of v. By Lemma 6.15, we may assume that all but
o(n) vertices are full.
Suppose that
for some vertex v. Then, since εkp → ∞, testing the relevant edges {u, v} one-by-
one, w.h.p we find one present in G p , forming, together with T , the required long
cycle. On the other hand, suppose that (6.13) fails for every v. Suppose that some
vertex v is full but poor. Since v has at most εk descendants, there are at least
(1 − 2ε)k pairs {u, v} ∈ R with u ∈ A (v). Since v has only one ancestor at each
distance, it follows that (6.13) holds for v, a contradiction.
We have shown that we can assume that no poor vertex is full. Hence there
are o(n) poor vertices, and we may apply Lemma 6.17, with X the set of vertices
that are not full. Let P be the path whose existence is guaranteed by the lemma,
110 Chapter 6. Spanning Subgraphs
and let Z be the set of vertices on P that are full and light, so |V (P) \ Z| ≤ ε 2 k. For
any v ∈ Z, since v is full, there are at least (1 − ε)k vertices u ∈ A (v) ∪ D(v) with
{u, v} ∈ R. Since (6.13) does not hold, at least (1 − 2ε)k of these vertices satisfy
d(u, v) ≤ (1−5ε)k. Since v is light, in turn at least 2εk of these u must be in A (v).
Recalling that a vertex has at most one ancestor at each distance, we find a set R(v)
of at least εk vertices u ∈ A (v) with {u, v} ∈ R and εk ≤ d(u, v) ≤ (1 − 5ε)k ≤ k.
It is now easy to find a (very) long cycle w.h.p. Recall that Z ⊆ V (P) with
|V (P) \ Z| ≤ ε 2 k. Thinking of P as oriented upwards towards the root, let v0 be the
lowest vertex in Z. Since |R(v0 )| ≥ εk and kp → ∞, w.h.p. there is an edge {u0 , v0 }
in G p with u0 ∈ R(v0 ). Let v1 be the first vertex below u0 along P with v1 ∈ Z. Note
that we go up at least εk steps from v0 to u0 and down at most 1+|V (P)\Z| ≤ 2ε 2 k
from u0 to v1 , so v1 is above v0 . Again w.h.p. there is an edge {u1 , v1 } in G p with
u1 ∈ R(v1 ), and so at least εk steps above v1 . Continue downwards from u1 to the
first v2 ∈ Z, and so on. Since ε −1 = O(1), w.h.p. −1we may continue in this way
to find overlapping chords {ui , vi } for 0 ≤ i ≤ 2ε , say. (Note that we remain
within P as each upwards step has length at most k.) These chords combine with
P to give a cycle of length at least (1 − 2ε −1 × 2ε 2 )k = (1 − 4ε)k, as shown in
Figure 6.6.
11
00 11
00 11
00 11
00 11
00 11
00 11
00 11
00 11
00 11
00
00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11
v0 v1 u0 v2 u1 v3 u2 v4 u3 u4
Figure 6.6: The path P, with the root off to the right. Each chord {vi , ui } has
length at least εk (and at most k); from ui to vi+1 is at most 2ε 2 k steps back along
P. The chords and the thick part of P form a cycle.
10 logbn/(∆2 + 1)c
p∆ > , (6.14)
bn/(∆2 + 1)c
then Gn,p contains an isomorphic copy of H w.h.p.
Proof. To prove this we first apply the Hajnal-Szemerédi Theorem to the square
H 2 of our graph H.
Recall that we square a graph if we add an edge between any two vertices of our
original graph which are at distance at most two. The Hajnal-Szemerédi Theorem
states that every graph with n vertices and maximum vertex degree at most d is
d + 1-colorable with all color classes of size bn/(d + 1)c or dn/(d + 1)e, i.e, the
(d + 1)-coloring is equitable.
Since the maximum degree of H 2 is at most ∆2 , there exists an equitable ∆2 + 1-
coloring of H 2 which induces a partition of the vertex set of H, say U = U(H),
into ∆2 + 1 pairwise disjoint subsets U1 ,U2 , . . . ,U∆2 +1 , so that each Uk is an in-
dependent set in H 2 and the cardinality of each subset is either bn/(∆2 + 1)c or
dn/(∆2 + 1)e.
Next, partition the set V of vertices of the random graph Gn,p into pairwise dis-
joint sets V1 ,V2 , . . . ,V∆2 +1 , so that |Uk | = |Vk | for k = 1, 2, . . . , ∆2 + 1.
We define a one-to-one function f : U 7→ V , which maps each Uk onto Vk resulting
in a mapping of H into an isomorphic copy of H in Gn,p . In the first step, choose
an arbitrary mapping of U1 onto V1 . Now U1 is an independent subset of H and so
Gn,p [V1 ] trivially contains a copy of H[U1 ]. Assume, by induction, that we have
already defined
(k)
graph Gm,m,p∗ has a perfect matching w.h.p. Moreover, we can conclude that the
(k) 1
probability that there is no perfect matching in Gm,m,p∗ is at most (∆2 +1)n . It is
here that we have used the extra factor 10 in the RHS of (6.14). We use a perfect
matching in G(k) (m, m, p∗ ) to define f , assuming that if xi and y j are matched then
f (ui ) = v j . To define our mapping f : U 7→ V we have to find perfect matchings
in all G(k) (m, m, p∗ ), k = 1, 2, . . . , ∆2 + 1. The probability that we can succeed in
this is at least 1 − 1/n. This implies that Gn,p contains an isomorphic copy of H
w.h.p.
1/4
Corollary 6.20. Let n = d 2 and p logn n , where ω(n), d → ∞. Then w.h.p.
Gn,p contains a copy of the 2-dimensional lattice Ld .
6.7 Exercises
6.7.1 Consider the bipartite graph process Γm , m = 0, 1, 2, . . . , n2 where we add
the n2 edges in A × B in random order, one by one. Show that w.h.p. the
hitting time for Γm to have a perfect matching is identical with the hitting
time for minimum degree at least one.
6.7.3 Show that if p = log n+(k−1)nlog log n+ω where k = O(1) and ω → ∞ then w.h.p.
Gn,n,p contains a k-regular spanning subgraph.
6.7.4 Consider the random bipartite graph G with bi-partition A, B where |A| =
|B| = n. Each vertex a ∈ A independently chooses d2 log ne random neigh-
bors in B. Show that w.h.p. G contains a perfect matching.
6.7. Exercises 113
6.7.5 Show that if p = log n+(k−1)nlog log n+ω where k = O(1) and ω → ∞ then w.h.p.
Gn,p contains bk/2c edge disjoint Hamilton cycles. If k is odd, show that
in addition there is an edge disjoint matching of size bn/2c. (Hint: Use
Lemma 6.4 to argue that after “peeling off” a few Hamilton cycles, we can
still use the arguments of Sections 6.1, 6.2).
6.7.6 Let m∗k denote the first time that Gm has minimum degree at least k. Show
that w.h.p. in the graph process (i) Gm∗1 contains a perfect matching and (ii)
Gm∗2 contains a Hamilton cycle.
6.7.7 Show that if p = log n+logn log n+ω where ω → ∞ then w.h.p.Gn,n,p contains
a Hamilton cycle. (Hint: Start with a 2-regular spanning subgraph from
(ii). Delete an edge from a cycle. Argue that rotations will always produce
paths beginning and ending at different sides of the partition. Proceed more
or less as in Section 6.2).
6.7.8 Show that if p = log n+logn log n+ω where n is even and ω → ∞ then w.h.p. Gn,p
contains a pair of vertex disjoint n/2-cycles. (Hint: Randomly partition [n]
into two sets of size n/2. Then move some vertices between parts to make
the minimum degree at least two in both parts).
6.7.9 Show that if three divides n and np2 log n then w.h.p. Gn,p contains n/3
vertex disjoint triangles. (Hint: Randomly partition [n] into three sets A, B,C
of size n/3. Choose a perfect matching M between A and B and then match
C into M).
6.7.10 Let G = (X,Y, E) be an arbitrary bipartite graph where the bi-partition X,Y
satisfies |X| = |Y | = n. Suppose that G has minimum degree at least 3n/4.
Let p = K log
n
n
where K is a large constant. Show that w.h.p. G p contains a
perfect matching.
6.7.11 Let p = (1+ε) logn n for some fixed ε > 0. Prove that w.h.p. Gn,p is Hamilton
connected i.e. every pair of vertices are the endpoints of a Hamilton path.
6.7.12 Show that if p = (1+ε)n log n for ε > 0 constant, then w.h.p. Gn,p contains a
copy of a caterpillar on n vertices. The diagram below is the case n = 16.
114 Chapter 6. Spanning Subgraphs
6.7.13 Show that for any fixed ε > 0 there exists cε such that if c ≥ cε then Gn,p
2
contains a cycle of length (1 − ε)n with probability 1 − e−cε n/10 .
6.7.14 Let p = (1+ε) logn n for some fixed ε > 0. Prove that w.h.p. Gn,p is pancyclic
i.e. it contains a cycle of length k for every 3 ≤ k ≤ n.
(See Cooper and Frieze [248] and Cooper [242], [244]).
6.7.16 Let T be a tree on n vertices and maximum degree less than c1 log n. Sup-
pose that T has at least c2 n leaves. Show that there exists K = K(c1 , c2 )
such that if p ≥ K log
n
n
then Gn,p contains a copy of T w.h.p.
6.7.17 Let p = 1000n and G = Gn,p . Show that w.h.p. any red-blue coloring of the
n
edges of G contains a mono-chromatic path of length 1000 . (Hint: Apply the
argument of Section 6.3 to both the red and blue sub-graphs of G to show
that if there is no long monochromatic path then there is a pair of large sets
S, T such that no edge joins S, T .)
This question is taken from Dudek and Pralat [312]
6.7.18 Suppose that p = n−α for some constant α > 0. Show that if α > 13 then
w.h.p. Gn,p does not contain a maximal spanning planar subgraph i.e. a
planar subgraph with 3n − 6 edges. Show that if α < 31 then it contains one
w.h.p. (see Bollobás and Frieze [167]).
6.7.19 Show that the hitting time for the existence of k edge-disjoint spanning trees
coincides w.h.p. with the hitting time for minimum degree k, for k = O(1).
(See Palmer and Spencer [723]).
6.7.20 Let p = nc where c > 1 is constant. Consider the greedy algorithm for con-
structing a large independent set I: choose a random vertex v and put v into
I. Then delete v and all of its neighbors. Repeat until there are no vertices
left. Use the differential equation method (see Section 6.4) and show that
w.h.p. this algorithm chooses an independent set of size at least logc c n.
6.7.21 Consider the modified greedy matching algorithm where you first choose
a random vertex x and then choose a random edge {x, y} incident with x.
Show that m = cn, that w.h.p. it produces a matching
applied to Gn,m , with
−2c )
of size 1
2 + o(1) − log(2−e
4c n.
6.8. Notes 115
7 log n
(a) Let p = 1−ε
n and let k = ε 2 . Show that w.h.p. there is no interval I of
length kn in [N] in which at least k of the variables take the value 1.
1+ε εn2
(b) Let p = n and let N0 = 2 . Show that w.h.p.
N0
ε(1 + ε)n
∑ Xi − ≤ n2/3 .
i=1 2
1−ε
6.7.23 Use the result of Exercise 6.7.21(a) to show that if p = n then w.h.p. the
maximum component size in Gn,p is at most 7 logε2
n
.
1+ε
6.7.24 Use the result of Exercise 6.7.21(b) to show that if p = n then w.h.p Gn,p
2
contains a path of length at least ε 5n .
6.8 Notes
Hamilton cycles
Multiple Hamilton cycles
There are several results pertaining to the number of distinct Hamilton cycles
in Gn,m . Cooper and Frieze [247] showed that in the graph process Gm∗2 con-
tains (log n)n−o(n) distinct Hamilton cycles w.h.p. This number
was improved by
n
Glebov and Krivelevich [435] to n!pn eo(n) for Gn,p and loge n eo(n) at time m∗2 .
McDiarmid [663] showed that for Hamilton cycles, perfect matchings, spanning
trees the expected number was much higher. This comes from the fact that al-
though there is a small probability that m∗2 is of order n2 , most of the expectation
comes from here. (m∗k is defined in Exercise 6.7.5).
Bollobás and Frieze [166] (see Exercise 6.7.4) showed that in the graph pro-
cess, Gm∗k contains bk/2c edge disjoint Hamilton cycles plus another edge disjoint
matching of size bn/2c if n is odd. We call this property Ak . This was the case
k = O(1). The more difficult case of the occurrence of Ak at m∗k , where k → ∞
was verified in two papers, Krivelevich and Samotij [601] and Knox, Kühn and
Osthus [574].
116 Chapter 6. Spanning Subgraphs
Long cycles
A sequence of improvements, Bollobás [150]; Bollobás, Fenner and Frieze [165]
to Theorem 6.8 in the sense of replacing O(log c/c) by something smaller led
finally to Frieze [384]. He showed that w.h.p. there is a cycle of length n(1 −
ce−c (1 + εc )) where εc → 0 with c. Up to the value of εc this is best possible.
Glebov, Naves and Sudakov [436] prove the following generalisation of (part
of) Theorem 6.5. They prove that if a graph G has minimum degree at least k and
k+ωk (1)
p ≥ log k+log log
k then w.h.p. G p has a cycle of length at least k + 1.
Spanning Subgraphs
Riordan [759] used a second moment calculation to prove the existence of a cer-
tain (sequence of) spanning subgraphs H = H (i) in Gn,p . Suppose that we denote
6.8. Notes 117
the number of vertices in a graph H by |H| and the number of edges by e(H).
Suppose that |H| = n. For k ∈ [n] we let eH (k) = max{e(F) : F ⊆ H, |F| = k} and
H (k)
γ = max3≤k≤n ek−2 . Riordan proved that if the following conditions hold, then
Gn,p contains a copy of H w.h.p.: (i) e(H) ≥ n, (ii) N p, (1 − p)n1/2 → ∞, (iii)
npγ /∆(H)4 → ∞.
This for example replaces the 12 in Corollary 6.19 by 14 .
Spanning trees
Gao, Pérez-Giménez and Sato [424] considered the existence of k edge disjoint
spanning trees in Gn,p . Using a characterisation
of Nash-Williams [707] they were
m
able to show that w.h.p. one can find min δ , n−1 edge disjoint spanning trees.
Here δ denotes the minimum degree and m denotes the number of edges.
When it comes to spanning trees of a fixed structure, Kahn conjectured that
the threshold for the existence of any fixed bounded degree tree T , in terms of
number of edges, is O(n log n). For example, a comb consists of a path P of length
n1/2 with each v ∈ P being one endpoint of a path Pv of the same length. The
paths Pv , Pw being vertex disjoint for v 6= w. Hefetz, Krivelevich and Szabó [477]
proved this for a restricted class of trees i.e. those with a linear number of leaves
or with an induced path of length Ω(n). Kahn, Lubetzky and Wormald [534],
[535] verified the conjecture for combs. Montgomery [686], [687] sharpened the
result for combs, replacing m = Cn log n by m = (1 + ε)n log n and proved that
any tree can be found w.h.p. when m = O(∆n(log n)5 ), where ∆ is the maximum
degree of T . More recently, Montgomery [689] improved the upper bound on m
to the optimal, m = O(∆n(log n)).
Large Matchings
Karp and Sipser [558] analysed a greedy algorithm for finding a large matching
in the random graph Gn,p , p = c/n where c > 0 is a constant. It has a much better
performance than the algorithm described in Section 6.4. It follows from their
work that if µ(G) denotes the size of the largest matching in G then w.h.p.
µ(Gn,p ) γ ∗ + γ∗ + γ ∗ γ∗
≈ 1−
n 2c
where γ∗ is the smallest root of x = c exp {−ce−x } and γ ∗ = ce−γ∗ .
Later, Aronson, Frieze and Pittel [52] tightened their analysis. This led to
δ ≥2 . Frieze and Pittel
the consideration of the size of the largest matching in Gn,m=cn
[413] showed that w.h.p. this graph contains a matching of size n/2 − Z where
Z is a random variable with bounded expectation. Frieze [389] proved that in
118 Chapter 6. Spanning Subgraphs
the bipartite analogue of this problem, a perfect matching exists w.h.p. Building
on this work, Chebolu, Frieze and Melsted [215] showed how to find an exact
maximum sized matching in Gn,m , m = cn in O(n) expected time.
H-factors
By an H-factor of a graph G, we mean a collection of vertex disjoint copies of
a fixed graph H that together cover all the vertices of G. Some early results on
the existence of H-factors in random graphs are given in Alon and Yuster [38]
and Ruciński [777]. For the case of when H is a tree, Łuczak and Ruciński [644]
found the precise threshold. For general H, there is a recent breakthrough paper
of Johansson, Kahn and Vu [529] that gives the threshold for strictly balanced H
and good estimates in general. See Gerke and McDowell [423] for some further
results.
Chapter 7
Extreme Characteristics
This chapter is devoted to the extremes of certain graph parameters. We look first
at the diameter of random graphs i.e. the extreme value of the shortest distance
between a pair of vertices. Then we look at the size of the largest independent set
and the the related value of the chromatic number. We decribe an important recent
result on “interpolation” that proves certain limits exist. We end the chapter with
the likely values of the first and second eigenvalues of a random graph.
7.1 Diameter
In this section we will first discuss the threshold for Gn,p to have diameter d,
when d ≥ 2 is a constant. The diameter of a connected graph G is the maximum
over distinct vertices v, w of dist(v, w) where dist(v, w) is the minimum number
of edges in a path from v to w. The theorem below was proved independently by
Burtin [203], [204] and by Bollobás [148]. The proof we give is due to Spencer
[809].
Theorem 7.1. Let d ≥ 2 be a fixed positive integer. Suppose that c > 0 and
Then (
e−c/2 if k = d
lim P(diam(Gn,p ) = k) =
n→∞ 1 − e−c/2 if k = d + 1.
111
000 000
111
Y 00
11 00
11
000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
000
111 000
111 00
11 00
11
000111
111
0000
1111 000
111
0001111
0000
1111 00
11
1111
0000000
111 00
11
0000
1111000
111
0000
1111 000
111
0000 111
1111 0000 0000
1111000
111
0000111
1111 0000
1111
0000111
0001111
1111111000
0000
1111 000
000
1110000
1111
0000
1111 0000
11110000000000
111
000
111
1111
0000 0001111
111
0000 111
1111 0000
1111 1111
0000111
000
0000111
1111 1111
0000
0001111000
111
0000111
0000 000
1111 000
1110000 0000111
1111 0000000
0001111
1111111
1111
0000
0000
1111 0001111
1110000
0000
1111 1111
0000
0000
1111000
000
1110000
0000
1111
000
111
000
111
0000 111
1111
0000
1111
000
000
1110000
1111
0000
1111 0000111
1111
0000
11110000000111
0001111
1111111
0000
000
000
111
0000
1111 000
111
000
1110000
1111
0000
1111 0000
1111000
1110000
1111000
111
000
111
000
111
0000
1111 000
111
000
1110000
1111 000
111
0000
1111 00
11
000
1110000
1111 00
11
000
111
000
111 000
111
0000 111
1111 000
000
111 000
111
000
111
0000
11110000000111
00
11
0000111
1111 1111
00
11
000
00
11
000
111
00
11
000
111
000
111 000
111
000
111 000
111
000
111 00
11
00
11 00
11
00
11
v X w
7.1. Diameter 121
So
P(∃v, w : dist(v, w) > d + 1) = o(n−1 ).
We now consider the probability that d or d + 1 is the diameter. We will use
Janson’s inequality, see Section 27.6. More precisely, we will use the earlier in-
equality, Corollary 27.14, from Janson, Łuczak and Ruciński [508].
We will first use this to estimate the probability of the following event: Let
v 6= w ∈ [n] and let
Let
Z = ∑ Zx ,
x
where (
1 if Bv,x,w occurs
Zx =
0 otherwise.
Janson’s inequality allows us to estimate the probability that Z = 0, which is pre-
cisely the probability of Av,w .
Now
2
d n 1
µ = E Z = (n − 2)(n − 3) · · · (n − d)p = log 1+O .
c n
∆= ∑ P(Bx ∩ By )
x,y:x6=y
v,x,w and v,y,w
share an edge
122 Chapter 7. Extreme Characteristics
d−1
d 2(d−1)−t 2d−t
≤ ∑ n p , t is the number of shared edges,
t=1 t
!
d−1 2d−t
2(d−1)−t− d−1
d (2d−t)
=O ∑n (log n) d
t=1
!
d−1
=O ∑ n−t/d+o(1)
t=1
= o(1).
i=1
and re-define
Z = ∑ Zx ,
x
7.1. Diameter 123
where now (
1 if Bx occurs
Zx =
0 otherwise.
then w.h.p.
2n
|N≤k0 | ≤ ∑ ((1 + γ)np)k ≤ 2((1 + γ)np)k0 = 3 + o(1)
k≤k0
log n
and so the diameter of Gn,p is at least (1 − o(1)) log np .
We can assume that np = no(1) as larger p are dealt with in Theorem 7.1. Now
fix v, w ∈ [n] and let Ni be as in the previous paragraph. Now consider a Breadth
First Search (BFS) that constructs N1 , N2 , . . . , Nk1 where
3 log n
k1 = .
5 log np
It follows that if (7.5) holds then for k ≤ k1 we have
Observe now that the edges from Ni to [n] \ N≤i are unconditioned by the BFS up
to layer k and so for x ∈ [n] \ N≤k ,
The events x ∈ Nk+1 are independent and so |Nk+1 | stochastically dominates the bi-
nomial Bin(n − n3/4 , ρk ). Assume inductively that |Nk | ≥ (1 − γ)k (np)k for some
k ≥ 1. This is true w.h.p. for k = 1 by (7.5). Let Ak be the event that (7.6) holds.
It follows that
E(|Nk+1 | | Ak ) ≥ np|Nk |(1 − O(n−1/5 )).
It then follows from the Chernoff bounds (Theorem 27.6) that
2
γ
P(|Nk+1 | ≤ ((1 − γ)np)k+1
≤ exp − |Nk |np = o(n−anyconstant ).
4
There is a small point to be made about conditioning here. We can condition
on (7.5) holding and then argue that this only multiplies small probabilities by
1 + o(1) if we use P(A | B) ≤ P(A)/ P(B).
It follows that if
log n log n
k2 = ≈
2(log np + log(1 − γ) 2 log np
then w.h.p. we have
|Nk2 | ≥ n1/2 .
7.2. Largest Independent Sets 125
Dense case
The following theorem was first proved by Matula [655].
1
Theorem 7.3. Suppose 0 < p < 1 is a constant and b = 1−p . Then w.h.p.
α(Gn,p ) ≈ 2 logb n.
Let
∆= ∑ P(Si , S j are independent in Gn,p ),
i, j
Si ∼S j
where S1 , S2 , . . . , S(n) are all the k-subsets of [n] and Si ∼ S j iff |Si ∩ S j | ≥ 2. By
k
Janson’s inequality, see Theorem 27.13,
(E Xk )2
P(Xk = 0) ≤ exp − .
2∆
Here we apply the inequality in the context of Xk being the number of k-cliques in
the complement of Gn,p . The set [N] will be the edges of the complete graph and
the sets Di will the edges of the k-cliques. Now
u j+1 k− j k− j
= (1 − p)− j
uj n − 2k + j + 1 j + 1
k (1 − p)− j
2
logb n
≤ 1+O .
n n( j + 1)
Therefore,
2 j−2
uj k 2(1 − p)−( j−2)( j+1)/2
≤ (1 + o(1))
u2 n j!
j−2
2k2 e
j+1
≤ (1 + o(1)) (1 − p)− 2 ≤ 1.
nj
So
(E Xk )2 1 n2 (1 − p)
≥ ≥ .
∆ ku2 k5
7.2. Largest Independent Sets 127
Therefore
2 /(log n)5 )
P(Xk = 0) ≤ e−Ω(n . (7.7)
Matula used the Chebyshev inequality and so he was not able to prove an
exponential bound like (7.7). This will be important when we come to discuss the
chromatic number.
Sparse Case
We now consider the case where p = d/n and d is a large constant. Frieze [388]
proved
Theorem 7.4. Let ε > 0 be a fixed constant. Then for d ≥ d(ε) we have that
w.h.p.
2n εn
α(Gn,p )) − (log d − log log d − log 2 + 1) ≤ .
d d
Dani and Moore [276] have given an even sharper result.
In this section we will prove that if p = d/n and d is sufficiently large then
w.h.p.
2 log d ε log d
α(Gn,p ) − n ≤ n. (7.8)
d d
This will follow from the following. Let Xk be as defined in the previous section.
Let
(2 − ε/8) log d (2 + ε/8) log d
k0 = n and k1 = n.
d d
Then,
(log d)2
ε log d
P α(Gn,p ) − E(α(Gn,p )) ≥ n ≤ exp −Ω n . (7.9)
8d d2
(log d)2
P(α(Gn,p ) ≥ k1 ) = P(Xk1 > 0) ≤ exp −Ω n . (7.10)
d
( ! )
(log d)3/2
P(α(Gn,p ) ≥ k0 ) = P(Xk0 > 0) ≥ exp −O n . (7.11)
d2
Let us see how (7.8) follows from these three inequalities. Indeed, (7.9) and (7.11)
imply that
ε log d
E(α(Gn,p )) ≥ k0 − n. (7.12)
8d
128 Chapter 7. Extreme Characteristics
t2
P(|Z − E(Z)| ≥ t) ≤ exp − .
2n − 2
ε log d
Setting t = 8d n yields (7.9).
Proof of (7.10): The first moment method gives
k1 !k1
d (2) d (k1 −1)/2
n ne
Pr(Xk1 > 0) ≤ 1− ≤ · 1−
k1 n k1 n
k1
(log d)2
de −(1+ε/5)
≤ ·d = exp −Ω n .
2 log d d
k0 n−k0 k0
1 E(Xk20 ) k −j j
= ∑ 0 n (1 − p)−(2)
j
≤ 2
P(Xk0 > 0) E(Xk0 ) j=0 k0
k0 2 j
k0 e jd jd
≤∑ · exp +O ×
j=0 j 2n n2
n − k0 k0 − j
j
k0
(7.14)
n n− j
k0 j
jd 2
k0 e k0 jd
≤∑ · · exp +O ×
j=0 j n 2n n2
7.2. Largest Independent Sets 129
(k0 − j)2
exp −
n− j
k0 j 2
k0 e k0 jd 2k0 k
≤b ∑ · · exp + × exp − 0
j=0 j n 2n n n
k0
= ∑ v j. (7.15)
j=0
So,
Now put
α log d 1 ε
j= n where 1/2 1/4
< α < 2− .
d d (log d) 4
Then
k0 e k0 jd 2k0 4e log d α log d 4 log d
· · exp + ≤ · exp +
j n 2n n αd 2 d
4e log d 4 log d
= 1−α/2
exp
αd d
< 1.
To see this note that if f (α) = αd 1−α/2 then f increases between d −1/2 and
2/ log d after which it decreases. Then note that
n
−1/2
o 4 log d
min f (d ), f (2 − ε) > 4e exp .
d
7.3 Interpolation
The following theorem is taken from Bayati, Gamarnik and Tetali [82]. Note that
it is not implied by Theorem 7.4. This paper proves a number of other results of
a similar flavor for other parameters. It is an important paper in that it verifies
some very natural conjectures about some graph parameters, that have not been
susceptible to proof until now.
Theorem 7.5. There exists a function H(d) such that
E(α(Gn,bdnc ))
lim = H(d).
n→∞ n
(A)
Proof. For this proof we use the model Gn,m of Section 1.3. This is proper since
we we know that w.h.p.
(A) (A)
|α(Gn,m ) − α(Gn,m )| ≤ ||E(Gn,m )| − m| ≤ log n.
(A)
Thus the sequence un = E(α(Gn,bdnc )) satisfies the conditions of Lemma 7.6 be-
low and the proof of Theorem 7.5 follows.
Proof of (7.17): We begin by constructing a sequence of graphs interpolating
(A) (A) (A)
between Gn,bdnc and a disjoint union of Gn1 ,m1 and Gn2 ,m2 . Given n, n1 , n2 such
that n1 + n2 = n and any 0 ≤ r ≤ m = bdnc, let G(n, m, r) be the random (pseudo-
)graph on vertex set [n] obtained as follows. It contains precisely m edges. The
first r edges e1 , e2 , . . . , er are selected randomly from [n]2 . The remaining m −
r edges er+1 , . . . , em are generated as follows. For each j = r + 1, . . . , m, with
probability n j /n, e j is selected randomly from M1 = [n1 ]2 and with probability
n2 /n, e j is selected randomly from M2 =[n1 + 1, n]2 . Observe that when r = m we
(A)
have G(n, m, r) = G(A) (n, m) and when r = 0 it is the disjoint union of Gn1 ,m1 and
(A)
Gn2 ,m2 where m j = Bin(m, n j /n) for j = 1, 2. We will show next that
(A)
E(α(Gn,m )) = E(α(G(n, m, m))) ≥
(A) (A)
E(α(G(n, m, 0))) = E(α(Gn1 ,m1 )) + E(α(Gn2 ,m2 ))
which is (7.17).
Proof of (7.19): Observe that G(n, m, r − 1) is obtained from
G(n, m, r) by deleting the random edge er and then adding an edge from M1 or M2 .
Let G0 be the graph obtained after deleting er , but before adding its replacement.
Remember that
G(n, m, r) = G0 + er .
We will show something stronger than (7.19) viz. that
Now let O∗ ⊆ [n] be the set of vertices that belong to every largest independent set
in G0 . Then for er = (x, y), α(G0 + e) = α(G0 ) − 1 if x, y ∈ O∗ and α(G0 + e) =
/ O∗ or y ∈
α(G0 ) if x ∈ / O∗ . Because er is randomly chosen, we have
2
|O∗ |
E(α(G0 + er ) | G0 ) − E(α(G0 )) = − .
n
By a similar argument
E(α(G(n, m, r − 1) | G0 ) − α(G0 )
n1 |O∗ ∩ M1 | 2 n2 |O∗ ∩ M2 | 2
=− −
n n1 n n2
n1 |O∗ ∩ M1 | n2 |O∗ ∩ M2 | 2
≤− +
n n1 n n2
∗ 2
|O |
=−
n
= E(α(G0 + er ) | G0 ) − E(α(G0 )),
Dense Graphs
We will first describe the asymptotic behavior of the chromatic number of dense
random graphs. The following theorem is a major result, due to Bollobás [156].
The upper bound without the 2 in the denominator follows directly from Theorem
7.3. An intermediate result giving 3/2 instead of 2 was already proved by Matula
[656].
1
Theorem 7.7. Suppose 0 < p < 1 is a constant and b = 1−p . Then w.h.p.
n
χ(Gn,p ) ≈ .
2 logb n
So assume that every set of order at least ν contains an independent set of order
at least k0 . We repeatedly choose an independent set of order k0 among the set
of uncolored vertices. Give each vertex in this set a new color. Repeat until the
number of uncolored vertices is at most ν. Give each remaining uncolored vertex
its own color. The number of colors used is at most
n n
+ν ≈ .
k0 2 logb n
7.4. Chromatic Number 133
It should be noted that Bollobás did not have the Janson inequality available
to him and he had to make a clever choice of random variable for use with the
Azuma-Hoeffding inequality. His choice was the maximum size of a family of
edge independent independent sets. Łuczak [637] proved the corresponding result
to Theorem 7.7 in the case where np → 0.
Concentration
Proof. Write
χ = Z(Y1 ,Y2 , . . . ,Yn ) (7.22)
where
Y j = {(i, j) ∈ E(Gn,p ) : i < j}.
Then
|Z(Y1 ,Y2 , . . . ,Yn ) − Z(Y1 ,Y2 , . . . , Ŷi , . . . ,Yn )| ≤ 1
and the theorem follows from the Azuma-Hoeffding inequality, see Section 27.7,
in particular Lemma 27.17.
Algorithm GREEDY
• A is the current set of vertices that might get color k in the current round.
begin
k ←− 0, A ←− [n], U ←− [n], Ck ←− 0./
while U 6= 0/ do
k ←− k + 1 A ←− U
while A 6= 0/
begin
Choose v ∈ A and put it into Ck
U ←− U \ {v}
A ←− A \ ({v} ∪ N(v))
end
end
1
Theorem 7.9. Suppose 0 < p < 1 is a constant and b = 1−p . Then w.h.p. algo-
rithm GREEDY uses approximately n/ logb n colors to color the vertices of Gn,p .
Proof. At the start of an iteration the edges inside U are un-examined. Suppose
that
n
|U| ≥ ν = .
(logb n)2
We show that approximately logb n vertices get color k i.e. at the end of round k,
|Ck | ≈ logb n.
Each iteration chooses a maximal independent set from the remaining uncolored
vertices. Let k0 = logb n − 5 logb logb n. Then
So the probability that we fail to use at least k0 colors while |U| ≥ ν is at most
1 3
ne− 3 (logb ν) = o(1).
Sparse Graphs
We now consider the case of sparse random graphs. We first state an important
conjecture about the chromatic number.
Conjecture: Let k ≥ 3 be a fixed positive integer. Then there exists dk > 0
such that if ε is an arbitrary positive constant and p = dn then w.h.p. (i) χ(Gn,p ) ≤ k
for d ≤ dk − ε and (ii) χ(Gn,p ) ≥ k + 1 for d ≥ dk + ε.
In the absence of a proof of this conjecture, we present the following result due
to Łuczak [638]. It should be noted that Shamir and Spencer [798] had already
proved six point concentration.
136 Chapter 7. Extreme Characteristics
Theorem 7.10. If p < n−5/6−δ , δ > 0, then the chromatic number of Gn,p is w.h.p.
two point concentrated.
(a) Let 0 < δ < 1/10, 0 ≤ p < 1 and d = np. Then w.h.p. each subgraph H of
Gn,p on less than nd −3(1+2δ ) vertices has less than (3/2 − δ )|H| edges.
(b) Let 0 < δ < 1.0001 and let 0 ≤ p ≤ δ /n. Then w.h.p. each subgraph H of
Gn,p has less than 3|H|/2 edges.
The above lemma can be proved easily by the first moment method, see Ex-
ercise 7.6.6. Note also that Lemma 7.11 implies that each subgraph H satisfying
the conditions of the lemma has minimum degree less than three, and thus is 3-
colorable, due to the following simple observation (see Bollobás [157] Theorem
V.1)
Lemma 7.12. Let k = maxH⊆G δ (H), where the maximum is taken over all in-
duced subgraphs of G. Then χ(G) ≤ k + 1.
1
P (χ(Gn,p ) ≤ k) > . (7.23)
log log n
Then w.h.p. all but at most n1/2 log n vertices of Gn,p can be properly colored
using k colors.
Proof. Let Z be the maximum number of vertices in Gn,p that can be properly
colored with k colors. Write Z = Z(Y1 ,Y2 , . . . ,Yn ) as in (7.22). Then we have
2
1 t
P(Z = n) > and P(|Z − E Z)| ≥ t) ≤ 2 exp − . (7.24)
log log n 2n
7.5. Eigenvalues 137
Putting t = 21 n1/2 log n into (7.24) shows that E Z ≥ n − t and the lemma follows
after applying the concentration inequality in (7.24) once again.
Now we are ready to present Łuczak’s ingenious argument to prove Theorem
7.10. Note first that when p is such that np → 0 as n → ∞, then by Theorem 2.1
Gn,p is a forest w.h.p. and so its chromatic number is either 1 or 2. Furthermore,
for 1/ log n < d < 1.0001 the random graph Gn,p w.h.p. contains at least one edge
and no subgraph with minimal degree larger than two (see Lemma 7.11), which
implies that χ(Gn,p ) is equal to 2 or 3 (see Lemma 7.12). Now let us assume that
the edge probability p is such that 1.0001 < d = np < n1/6−δ . Observe that in this
range of p the random graph Gn,p w.h.p. contains an odd cycle, so χ(Gn,p ) ≥ 3.
Let k be as in Lemma 7.13 and let U0 be a set of size at most u0 = n1/2 log n
such that [n] \U0 can be properly colored with k colors. Let us construct a nested
sequence of subsets of vertices U0 ⊆ U1 ⊆ . . . ⊆ Um of Gn,p , where we define
Ui+1 = Ui ∪ {v, w}, where v, w 6∈ Ui are connected by an edge and both v and w
have a neighbor in Ui . The construction stops at i = m if such a pair {v, w} does
not exist.
Notice that m can not exceed m0 = n1/2 log n, since if m > m0 then a subgraph of
Gn,p induced by vertices of Um0 would have
vertices and at least 3m0 ≥ (3/2 − δ )|Um0 | edges, contradicting the statement of
Lemma 7.11.
As a result, the construction produces a set Um in Gn,p , such that its size is smaller
than nd −3(1+2δ ) and, moreover, all neighbors N(Um ) of Um form an independent
set, thus “isolating” Um from the “outside world”.
Now, the coloring of the vertices of Gn,p is an easy task. Namely, by Lemma 7.13,
we can color the vertices of Gn,p outside the set Um ∪ N(Um ) with k colors. Then
we can color the vertices from N(Um ) with color k + 1, and finally, due to Lemmas
7.11 and 7.12, the subgraph induced by Um is 3-colorable and we can color Um
with any three of the first k colors.
7.5 Eigenvalues
Separation of first and remaining eigenvalues
The following theorem is a weaker version of a theorem of Füredi and Komlós
[421], which was itself a strengthening of a result of Juhász [533]. See also Coja–
Oghlan [232] and Vu [842]. In their papers, 2ω log n is replaced by 2 + o(1) and
this is best possible.
138 Chapter 7. Extreme Characteristics
where
kMk = max |Mx| = max {|λ1 (M)|, |λn (M)|} .
|x|=1
We first show that the lemma implies the theorem. Let e denote the all 1’s vector.
Suppose that |ξ | = 1 and ξ ⊥e. Then Jξ = 0 and
p
|Aξ | = |Mξ | ≤ kMk ≤ 2ω log n np(1 − p).
Now let |x| = 1 and let x = αu + β y where u = √1 e and y⊥e and |y| = 1. Then
n
= |pJu| − |Mu|
p
≥ np − 2ω log n np(1 − p),
|Aξ |
≤ max
06=ξ ⊥u |ξ |
|Mξ |
≤ max
06=ξ ⊥u |ξ |
p
≤ 2ω log n np(1 − p)
λn = min ξ T Aξ ≥ min ξ T Aξ − pξ T Jξ
|ξ |=1 |ξ |=1
p
= min −ξ T Mξ ≥ −kMk ≥ −2ω log n np(1 − p).
|ξ |=1
(i) E mi j = 0
(ii) Var mi j ≤ p(1 − p) = σ 2
(iii) mi j , mi0 j0 are independent, unless (i0 , j0 ) = ( j, i),
in which case they are identical.
We estimate
kM̂k ≤ Trace(M̂ k )1/k ,
where k = ω log n.
Now,
Recall that the i, jth entry of M̂ k is the sum over all products
mi,i1 mi1 ,i2 · · · mik−1 j .
Continuing, we therefore have
k
E kM̂kk ≤ ∑ En,k,ρ
ρ=2
where !
k−1
En,k,ρ = ∑ E ∏ mi j i j+1 .
i0 ,i1 ,...,ik−1 ∈[n] j=0
|{i0 ,i1 ,i2 ,...,ik−1 }|=ρ
if the walk W (i) contains an edge that is crossed exactly once, by condition (i).
On the other hand, |mi j | ≤ 1 and so by conditions (ii), (iii),
!
k−1
E ∏ mi j i j+1 ≤ σ 2(ρ−1)
j=0
where nρ bounds from above the the number of choices of ρ distinct vertices,
while kk bounds the number of walks of length k.
We have
1 1
2 k+1 2 k+1 1
E kM̂kk ≤ ∑ Rk,ρ σ 2(ρ−1) ≤ ∑ nρ kk σ 2(ρ−1) ≤ 2n 2 k+1 kk σ k .
ρ=2 ρ=2
Therefore,
E kM̂kk
1 k
1
k
P kM̂k ≥ 2kσ n = P kM̂k ≥ 2kσ n
2 2 ≤
1 k
2kσ n 2
1
!k k
2n 2 k+1 kk σ k (2n)1/k
1
≤ = = + o(1) = o(1).
1 k 2 2
2kσ n 2
p
It follows that w.h.p. kM̂k ≤ 2σ ω(log n)n1/2 ≤ 2ω log n np(1 − p) and com-
pletes the proof of Theorem 7.14.
Concentration of eigenvalues
We show here how one can use Talagrand’s inequality, Theorem 27.18, to show
that the eigenvalues of random matrices are highly concentrated around their me-
dian values. The result is from Alon, Krivelevich and Vu [35].
Theorem 7.16. Let A be an n × n random symmetric matrix with independent en-
tries ai, j = a j,i , 1 ≤ i ≤ j ≤ n with absolute value at most one. Let its eigenvalues
be λ1 (A) ≥ λ2 (A) ≥ · · · ≥ λn (A). Suppose that 1 ≤ s ≤ n. Let µs denote the me-
dian value of λs (A) i.e. µs = infµ {P(λs (A) ≤ µ) ≥ 1/2}. Then for any t ≥ 0 we
have
2 2
P(|λs (A) − µs | ≥ t) ≤ 4e−t /32s .
The same estimate holds for the probability that λn−s+1 (A) deviates from its me-
dian by more than t.
Fix B ∈ B and let v(1) , v(2) , . . . , v(s) be an orthonormal set of eigenvectors for
(k) (k) (k)
the s largest eigenvalues of B. Let v(k) = (v1 , v2 , . . . , vn ),
s
(k) 2
αi,i = ∑ (vi ) for 1 ≤ i ≤ n
k=1
and s s
s s
(k) (k) 2
αi, j = 2 ∑ (vi )2 ∑ (v j ) for 1 ≤ i < j ≤ n.
k=1 k=1
Lemma 7.17.
∑ αi,2 j ≤ 2s2 .
1≤i≤ j≤n
Proof.
!2 !
n s s s
(k) 2 (k) 2 (k) 2
∑ αi,2 j = ∑ ∑ (vi ) +4 ∑ ∑ (vi ) ∑ (v j )
1≤i≤ j≤n i=1 k=1 1≤i< j≤n k=1 k=1
!2 !2
n s s n
(k) (k) 2
≤2 ∑ ∑ (vi )2 =2 ∑ ∑ (vi ) = 2s2 ,
i=1 k=1 k=1 i=1
where we have used the fact that each v(k) is a unit vector.
∑ αi, j ≥ t/2.
1≤i≤ j≤n:ai, j 6=bi, j
Fix A ∈ A . Let u = ∑sk=1 ck v(k) be a unit vector in the span S of the vectors
v(k) , k = 1, 2, . . . , s which is orthogonal to the eigenvectors of the (s − 1) largest
eigenvalues of A. Recall that v(k) , k = 1, 2, . . . , s are eigenvectors of B. Then
∑sk=1 c2k = 1 and ut Au ≤ λs (A) ≤ M, whereas ut Bu ≥ minv∈S vt Bv = λs (B) ≥ M +
t. Recall that all entries of A and B are bounded in absolute value by 1, implying
that |bi, j − ai, j | ≤ 2 for all 1 ≤ i, j ≤ n. It follows that if X is the set of ordered
pairs (i, j) for which ai, j 6= bi, j then
!t
s s
t (k) (k)
t ≤ u (B − A)u = ∑ (bi, j − ai, j ) ∑ ck vi ∑ ck v j
(i, j)∈X k=1 k=1
s s
(k) (k)
≤2 ∑ ∑ ck vi ∑ ck v j
(i, j)∈X k=1 k=1
7.6. Exercises 143
s s ! s s !
s s 2 s s
2
(k) (k)
≤2 ∑ ∑ c2k ∑ vi ∑ c2k ∑ vj
(i, j)∈X k=1 k=1 k=1 k=1
=2 ∑ αi, j
(i, j)∈X
as claimed. (We obtained the third inequality by use of the Cauchy-Schwarz in-
equality).
By the above two lemmas, and by Theorem 27.18 for every M and every t > 0
2 /(32s2 )
P(λs (A) ≤ M) P(λs (B) ≥ M + t) ≤ e−t . (7.26)
7.6 Exercises
7.6.1 Let p = d/n where d is a positive constant. Let S be the set of vertices of
2 log n
degree at least 3 log log n . Show that w.h.p., S is an independent set.
7.6.2 Let p = d/n where d is a large positive constant. Use the first moment
method to show that w.h.p.
2n
α(Gn,p ) ≤ (log d − log log d − log 2 + 1 + ε)
d
for any positive constant ε.
7.6.3 Complete the proof of Theorem 7.4.
Let m = d/(log d)2 and partition [n] into n0 = mn sets S1 , S2 , . . . , Sn0 of size
m. Let β (G) be the maximum size of an independent set S that satisfies
|S ∩ Si | ≤ 1 for i = 1, 2, . . . , n0 . Use the proof idea of Theorem 7.4 to show
that w.h.p.
2n
β (Gn,p ) ≥ k−ε = (log d − log log d − log 2 + 1 − ε).
d
144 Chapter 7. Extreme Characteristics
7.6.8 A topological clique of size s is a graph obtained from the complete graph
Ks by subdividing edges. Let tc(G) denote the size of the largest topological
clique contained in a graph G. Prove that w.h.p. tc(Gn,1/2 ) = Θ(n1/2 ).
7.6.10 Show that if d > 2k log k for a positive integer k ≥ 2 then w.h.p. G(n, d/n) is
not k-colorable. (Hint:Consider the expected number of proper k-coloring’s).
7.6.11 Let p = K log n/n for some large constant K > 0. Show that w.h.p. the
diameter of Gn,p is Θ(log n/ log log n).
7.6.12 Suppose that 1 + ε ≤ np = o(log n), where ε > 0 is constant. Show that
given A > 0, there exists B = B(A) such that
log n
P diam(K) ≥ B ≤ n−A ,
log np
7.6.13 Let p = d/n for some constant d > 0. Let A be the adjacency matrix of
Gn,p . Show that w.h.p. λ1 (A) ≈ ∆1/2 where ∆ is the maximum degree in
Gn,p . (Hint: the maximum eigenvalue of the adjacency matrix of K1,m is
m1/2 ).
7.6.15 The set chromatic number χs (G) of a graph G = (V, E) is defined as follows:
Let C denote a set of colors. Color each v ∈ V with a color f (v) ∈ C.
Let Cv = { f (w) : {v, w} ∈ G}. The coloring is proper if Cv 6= Cw whenever
{v, w} ∈ E. χs is the minimum size of C in a proper coloring of G. Prove
that if 0 < p < 1 is constant then w.h.p. χs (Gn,p ) ≈ r log2 n where r = log 21/s
2
and s = min q2` + (1 − q` )2 : ` = 1, 2, . . . where q = 1 − p. (This question
7.7 Notes
Chromatic number
There has been a lot of progress in determining the chromatic number of sparse
random graphs. Alon and Krivelevich [32] extended the result in [638] to the
range p ≤ n−1/2−δ . A breakthrough came when Achlioptas and Naor [6] identi-
fied the two possible values for np = d where d = O(1): Let kd be the smallest
integer k such that d < 2k log k. Then w.h.p. χ(Gn,p ) ∈ {kd , kd + 1}. This im-
plies that dk , the (conjectured) threshold for a random graph to have chromatic
number at most k, satisfies dk ≥ 2k log k − 2 logk −2 + ok (1) where ok (1) → 0 as
k → ∞. Coja–Oghlan, Panagiotou and Steger [234] extended the result of [6]
to np ≤ n1/4−ε , although here the guaranteed range is three values. More re-
cently, Coja–Oghlan and Vilenchik [235] proved the following. Let dk,cond =
2k log k − log k − 2 log 2. Then w.h.p. dk ≥ dk,cond − ok (1). On the other hand
Coja–Oghlan [233] proved that dk ≤ dk,cond + (2 log 2 − 1) + ok (1).
It follows from Chapter 2 that the chromatic number of Gn,p , p ≤ 1/n is w.h.p.
at most 3. Achlioptas and Moore [4] proved that in fact χ(Gn,p ) ≤ 3 w.h.p. for
p ≤ 4.03/n. Now a graph G is s-colorable iff it has a homomorphism ϕ : G → Ks .
(A homomorphism from G to H is a mapping ϕ : V (G) → V (H) such that if
{u, v} ∈ E(G) then (ϕ(u), ϕ(v)) ∈ E(H)). It is therefore of interest in the con-
text of coloring, to consider homomorphisms from Gn,p to other graphs. Frieze
and Pegden [411] show that for any ` > 1 there is an ε > 0 such that with high
probability, Gn, 1+ε either has odd-girth < 2` + 1 or has a homomorphism to the
n
odd cycle C2`+1 . They also showed that w.h.p. there is no homomorphism from
Gn,p , p = 4/n to C5 . Previously, Hatami [470] has shown that w.h.p. there is no
homomorphism from a random cubic graph to C7 .
Alon and Sudakov [37] considered how many edges one must add to Gn,p in
order to significantly increase the chromatic number. They show that if n−1/3+δ ≤
p ≤ 1/2 for some fixed δ > 0 then w.h.p. for every set E of
2−12 ε 2 n2
(log (np))2
edges, the chromatic number of Gn,p ∪ E is still at most 2 (1+ε)n
log (np) .
b b
146 Chapter 7. Extreme Characteristics
Algorithmic questions
We have seen that the Greedy algorithm applied to Gn,p generally produces a
coloring that uses roughly twice the minimum number of colors needed. Note
also that the analysis of Theorem 7.9, when k = 1, implies that a simple greedy
algorithm for finding a large independent set produces one of roughly half the
maximum size. In spite of much effort neither of these two results have been sig-
nificantly improved. We mention some negative results. Jerrum [526] showed that
the Metropolis algorithm was unlikely to do very well in finding an independent
set that was significantly larger than GREEDY. Other earlier negative results in-
clude: Chvátal [228], who showed that for a significant set of densities, a large
class of algorithms will w.h.p. take exponential time to find the size of the largest
independent set and McDiarmid [660] who carried out a similar analysis for the
chromatic number.
Frieze, Mitsche, Pérez-Giménez and Pralat [409] study list coloring in an on-
line setting and show that for a wide range of p, one can asymptotically match the
best known constants of the off-line case. Moreover, if pn ≥ logω n, then they get
the same multiplicative factor of 2 + o(1).
let Ωk (G) be the set of proper k-coloring’s of the vertices of G. There has been a
good deal of work on the problem of efficiently choosing a (near) random member
of Ωk (G). For example, Vigoda [839] has described an algorithm that produces a
(near) random sample in polynomial time provided k > 11∆(G)/6. When it comes
to Gn,p , Dyer, Flaxman, Frieze and Vigoda [321] showed that if p = d/n, d = O(1)
then w.h.p. one can sample a random coloring if k = O(log log n) = o(∆). The
bound on k was reduced to k = O(d O(1) ) by Mossell and Sly [696] and then to
k = O(d) by Efthymiou [327].
Inhomogeneous Graphs
Thus far we have concentrated on the properties of the random graphs Gn,m and
Gn,p . We first consider a generalisation of Gn,p where the probability of edge
(i, j) is pi j is not the same for all pairs i, j. We call this the generalized binomial
graph . Our main result on this model concerns the probability that it is connected.
For this model we concentrate on its degree sequence and the existence of a giant
component. After this we move onto a special case of this model, viz. the expected
degree model. Here pi j is proportional to wi w j for weights wi . In this model, we
prove results about the size of the largest components. We finally consider another
special case of the generalized binomial graph, viz. the Kronecker random graph.
Note that Qi is the probability that vertex i is isolated and λn is the expected
number of isolated vertices. Next let
Rik = min qi j1 · · · qi jk .
1≤ j1 < j2 <···< jk ≤n
152 Chapter 8. Inhomogeneous Graphs
Suppose that the edge probabilities pi j are chosen in such a way that the following
conditions are simultaneously satisfied as n → ∞:
max Qi → 0, (8.1)
1≤i≤n
Theorem 8.1. Let X0 denote the number of isolated vertices in the random graph
Gn,P . If conditions (8.1) (8.2) and (8.3) hold, then
λ k −λ
lim P(X0 = k) = e
n→∞ k!
for k = 0, 1, . . ., i.e., the number of isolated vertices is asymptotically Poisson
distributed with mean λ .
Proof. Let (
1 with prob. pi j
Xi j =
0 with prob. qi j = 1 − pi j .
Denote by Xi , for i = 1, 2, . . . n, the indicator of the event that vertex i is isolated
in Gn,P . To show that X0 converges in distribution to the Poisson random variable
with mean λ one has to show (see Theorem 26.11) that for any natural number k
!
λk
E ∑ X X
i1 i2 · · · Xik → (8.4)
1≤i1 <i2 <...<ik ≤n k!
as n → ∞. But
k
E (Xi1 Xi2 · · · Xik ) = ∏ P Xir = 1|Xi1 = . . . = Xir−1 = 1 , (8.5)
r=1
8.1. Generalized Binomial Graph 153
1
∑ Qi1 · · · Qik = ∑ Qi1 · · · Qik ≥
1≤i1 <···<ik ≤n k! 1≤i
1 6=···6=ir ≤n
!
1 k n 2
Q · · · Q − ∑ Qi Qi1 · · · Qik−2
k! 1≤i1 ∑ ∑
i1 ik
,...,ik ≤n k! i=1 1≤i1 ,...,ik−2 ≤n
λnk λk λk
≥ − (max Qi )λnk−1 = n − (max Qi )λnk−1 → , (8.7)
k! i k! i k!
as n → ∞.
Now,
n n
Qi
∑ ≥ λn = ∑ Qi,
i=1 Rik i=1
k
n/2 1
and if lim sup ∑ni=1 RQiki n Qi
> λ then lim sup ∑k=1 k! ∑i=1 Rik > eλ − 1, which con-
n→∞ n→∞
tradicts (8.3). It follows that
n
Qi
lim
n→∞
∑ Rik = λ .
i=1
Therefore !k
n
1 Qi λk
∑ Qi1 · · · Qik ≤ k! ∑ Rik →
k!
.
1≤i1 <...<ik ≤n i=1
154 Chapter 8. Inhomogeneous Graphs
as n → ∞.
Combining this with (8.7) gives us (8.4) and completes the proof of Theorem
8.1.
One can check that the conditions of the theorem are satisfied when
log n + xi j
pi j = ,
n
where xi j ’s are uniformly bounded by a constant.
The next theorem shows that under certain circumstances, the random graph
Gn,P behaves in a similar way to Gn,p at the connectivity threshold.
Theorem 8.2. If the conditions (8.1), (8.2) and (8.3) hold, then
Proof. To prove the this we will show that if (8.1), (8.2) and (8.3) are satisfied
then w.h.p. Gn,P consists of X0 + 1 connected components, i.e., Gn,P consists of
a single giant component plus components that are isolated vertices only. This,
together with Theorem 8.1, implies the conclusion of Theorem 8.2.
Let U ⊆ V be a subset of the vertex set V . We say that U is closed if Xi j = 0 for
every i and j, where i ∈ U and j ∈ V \ U. Furthermore, a closed set U is called
simple if either U or V \ U consists of isolated vertices only. Denote the number
of non-empty closed sets in Gn,P by Y1 and the number of non-empty simple sets
by Y . Clearly Y1 ≥ Y .
We will prove first that
λk
lim P(Y = 2k+1 − 1) = e−λ .
n→∞ k!
Observe that for any ` ≥ 0,
`
EY ≥ ∑ (2k+1 − 1) P(Y = 2k+1 − 1)
k=0
8.1. Generalized Binomial Graph 155
and hence
`
λ k e−λ
lim inf EY ≥
n→∞
∑ (2k+1 − 1) k!
.
k=0
So,
`
λ k e−λ
lim inf EY ≥ lim
n→∞
∑ (2k+1 − 1)
`→∞ k=0 k!
= 2eλ − 1
To prove (8.9) denote by Zk the number of closed sets of order k in Gn,P so that
Y1 = ∑nk=1 Zk . Note that
Zk = ∑ Zi1 ...ik ,
i1 <...<ik
Hence !k
n
Qi 1 Qi
E Zk ≤ ∑ ∏ ≤ ∑ Rik .
i1 <...<ik i∈Ik Rik k! i=1
n/2
lim sup ∑ E Zk ≤ eλ − 1.
n→∞ k=1
To complete the estimation of E Zk (and thus for EY1 ) consider the case when
k > n/2. For convenience let us switch k with n − k, i.e, consider E Zn−k , when
0 ≤ k < n/2. Notice that E Zn = 1 since V is closed. So for 1 ≤ k < n/2
E Zn−k = ∑ ∏ qi j .
i1 <...<ik i∈Ik , j6∈Ik
156 Chapter 8. Inhomogeneous Graphs
i.e., asymptotically, the probability that there is a closed set that is not simple,
tends to zero as n → ∞. It is easy to check that X0 < n w.h.p. and therefore
Y = 2X0 +1 − 1 w.h.p. and so w.h.p. Y1 = 2X0 +1 − 1. If Gn,P has more than X0 + 1
connected components then the graph after removal of all isolated vertices would
contain at least one closed set, i.e., the number of closed sets would be at least
2X0 +1 . But the probability of such an event tends to zero and the theorem follows.
∑ pi j ≥ c log n,
i∈S, j∈V \S
Hence the expected number of isolated vertices of Hi does not exceed |U|e−1 .
Therefore, by the Markov inequality, it is at most 2|U|e−1 with probability at least
1/2. But in this case the number of connected components of Hi is at most
−1 1 −1 1 −1
2|U|e + (|U| − 2|U|e ) = +e |U| < 0.9|U|,
2 2
and so (8.12) follows. Observe that if Ck > 1 then the total number of successful
stages is strictly less than log n/ log 0.9 < 10 log n. However, by (8.12), the proba-
bility of this event is at most the probability that a Binomial random variable with
parameters k and 1/2 will attain a value at most 10 log n. It follows from (27.22)
that if k = c log n = (20 + t) log n then the probability that Ck > 1 (i.e., that G0p0
e
2
is disconnected) is at most n−t /4c . This completes the proof of (8.11) and the
theorem follows.
We assume that maxi w2i < W so that pi j ≤ 1. The resulting graph is denoted as
Gn,Pw . Note that putting wi = np for i ∈ [n] yields the random graph Gn,p .
Notice that loops are allowed here but we will ignore them in what follows.
Moreover, for vertex i ∈ V its expected degree is
wi w j
∑ = wi .
j W
Denote the average vertex weight by w (average expected vertex degree) i.e.,
W
w= ,
n
while, for any subset U of a vertex set V define the volume of U as
w(U) = ∑ wk .
k∈U
8.2. Expected Degree Model 159
Chung and Lu in [220] and [222] proved the following results summarized in
the next theorem.
Theorem 8.4. The random graph Gn,Pw with a given expected degree sequence
has a unique giant component w.h.p. if the average expected degree is strictly
greater than one (i.e., w > 1). Moreover, if w > 1 then w.h.p. the giant component
has volume √
λ0W + O n(log n)3.5 ,
where λ0 is the unique nonzero root of the following equation
n n
∑ wie−wiλ = (1 − λ ) ∑ wi,
i=1 i=1
(1 + o(1)µ(w) log n,
where (
1/(w − 1 − log w) if 1 < w < 2,
µ(w) =
1/(1 + log w − log 4) if w > 4/e.
Here we will prove a weaker and restricted version of the above theorem. In
the current context, a giant component is one with volume Ω(W ).
Theorem 8.5. If the average expected degree w > 4, then a random graph Gn,Pw
w.h.p. has a unique giant component and its volume is at least
2
1− √ W
ew
while the second-largest component w.h.p. has the size at most
log n
(1 + o(1)) .
1 + log w − log 4
The proof is based on a key lemma given below, proved under stronger condi-
tions on w than in fact Theorem 8.5 requires.
4
Lemma 8.6. For any positive ε < 1 and w > e(1−ε) 2 w.h.p. every connected
component in the random graph Gn,Pw either has volume at least εW or has at
log n
most 1+log w−log 4+2 log(1−ε) vertices.
160 Chapter 8. Inhomogeneous Graphs
where
1 1
=ρ := .
W nw
So, the probability that S induces a connected subgraph of our random graph can
be bounded from above by
∑ P(T ) = ∑ ∏ wi j wil ρ,
T T {vi j ,vi }∈E(T )
l
where the sum ranges over all S ⊆ V, |S| = k. Now, we focus our attention on k-
vertex components whose volume is at most εW . We call such components small
or ε-small. So, if Yk is the number of small components of size k in Gn,Pw then
The function x2k−2 e−x(1−ε) achieves its maximum at x = (2k − 2)/(1 − ε). There-
fore
2k − 2 2k−2 −(2k−2)
k−1
n ρ
f (k) ≤ e
k kk 1−ε
ne k ρ k−1 2k − 2 2k−2
≤ e−(2k−2)
k kk 1−ε
2k
(nρ)k
2
≤ 2
e−k
4ρ(k − 1) 1 − ε
k
1 4
=
4ρ(k − 1)2 ew(1 − ε)2
e−ak
= ,
4ρ(k − 1)2
where
a = 1 + log w − log 4 + 2 log(1 − ε) > 0
under the assumption of Lemma 8.6.
Let k0 = loga n . When k satisfies k0 < k < 2k0 we have
1 1
f (k) ≤ =o ,
4nρ(k − 1)2 log n
162 Chapter 8. Inhomogeneous Graphs
2 log n
while, when a ≤ k ≤ n, we have
1 1
f (k) ≤ 2 =o .
4n ρ(k − 1)2 n log n
So, the probability that there exists an ε-small component of size exceeding k0 is
at most
log n 1 1
∑ f (k) ≤ a × o log n + n × o n log n = o(1).
k>k0
To prove Theorem 8.5 assume that for some fixed δ > 0 we have
4 2
w = 4+δ = 2
where ε = 1 − (8.16)
e (1 − ε) (ew)1/2
Hence
1/2 1/3 δ
W ≤n +2 1+ n1/2 .
8
This is a contradiction since for our choice of w
W = nw ≥ 4(1 + δ )n.
8.2. Expected Degree Model 163
1 + δ8
wi w j ρ ≥ w2i0 ρ ≥ .
i0
So the asymptotic behavior of G can be approximated by a random graph Gn,p
with n = i0 and p > 1/i0 . So, w.h.p. G has a component of size Θ(i0 ) = Ω(n1/3 ).
Applying Lemma 8.6 with ε as in (8.16) we see that any component with size
log n has volume at least εW .
Finally, consider the volume of a giant component. Suppose first that there
exists a giant component of volume cW which is ε-small i.e. c ≤ ε. By Lemma
8.6, the size of the giant component is then at most 2log n
log 2 . Hence, there must be at
least one vertex with weight w greater than or equal to the average
2cW log 2
w≥ .
log n
But it implies that w2 W , which contradicts the general assumption that all
pi j < 1.
We now prove uniqueness in the same way that we proved the uniqueness of
the giant component in Gn,p . Choose η > 0 such that w(1 − η) > 4. Then define
w0i = (1 − η)wi and decompose
Gn,Pw = G1 ∪ G2
w0i w0j
where the edge probability in G1 is p0i j = (1−η)W and the edge probability in G2
wi w j ηw w
is p00i j where 1 − W= (1 − p0i, j )(1 − p00i j ). Simple algebra gives p00i j ≥ Wi j . It
follows from the previous analysis that G1 contains between one and 1/ε giant
components. Let C1 ,C2 be two such components. The probability that there is no
G2 edge between them is at most
ηwi w j ηw(C1 )w(C2 )
∏ 1 − W ≤ exp − ≤ e−ηW = o(1).
i∈C1 W
j∈C2
Notice that
∑ j w2j W
= ≥ w2
= w.
W n
Chung and Lu [220] proved the following.
Theorem 8.7. If the
2
average expected square degree w2 < 1 then, with probability
w w2 √
at least 1 − 2 2 , all components of Gn,Pw have volume at most C n.
C 1−w
Proof. Let
x = P(∃S : w(S) ≥ Cn1/2 and S is a component).
Randomly choose two vertices u and v from V , each with probability proportional
to its weight.
√ Then, for√each vertex, the probability that it is in a set S with
w(S) ≥ C n is at least C nρ. Hence the probability that both vertices are in the
same component is at least
√
x(C nρ)2 = C2 xnρ 2 . (8.18)
On the other hand, for any two fixed vertices, say u and v, the probability Pk (u, v)
of u and v being connected via a path of length k + 1 can be bounded from above
as follows
Recall that the probabilities of u and v being chosen from V are wu ρ and wv ρ,
respectively. so the probability that a random pair of vertices are in the same
component is at most
2
wu wv ρ w2 ρ
∑ wuρ wvρ = .
u,v 1 − w2 1 − w2
which implies
2
w w2
x≤ ,
C2 1 − w2
and Theorem 8.7 follows.
where 0 < α, β , γ < 1, and let P[k] be the kth Kronecker power of P. Here P[k] is
obtained from P[k−1] as in the diagram below:
[k−1]
β P[k−1]
[k] αP
P =
β P[k−1] γP[k−1]
β 2 β γ γβ γ 2
Note that P[k] is symmetric and has size 2k × 2k .
We define a Kronecker random graph as a copy of Gn,P[k] for some k ≥ 1 and
n = 2k . Thus each vertex is a binary string of length k, and between any two such
vertices (strings) u, v we put an edge independently with probability
or equivalently
puv = α i β j γ k−i− j ,
where i is the number of positions t such that ut = vt = 1, j is the number of t
where ut 6= vt and hence k − i − j is the number of t that ut = vt = 0. We observe
that when α = β = γ then Gn,P[k] becomes Gn,p with n = 2k and p = α k .
166 Chapter 8. Inhomogeneous Graphs
Connectivity
We will first examine, following Mahdian and Xu [647], conditions under which
is Gn,P[k] connected w.h.p.
k (k)
j
P(0 is isolated) = ∏(1 − p0v ) ≥ ∏ 1 − β j γ k− j
v j=0
(
k k j k− j )
j β γ
≥ exp − ∑ = e−1/ζ .
j=0 1−ζ
Now when α = β = 1, γ = 0, the vertex with all 1’s has degree n − 1 with proba-
bility one and so Gn,P[k] will be connected w.h.p. in this case.
It remains to show that the condition β + γ > 1 is also sufficient. To show that
β + γ > 1 implies connectivity we will apply Theorem 8.3. Notice that the ex-
pected degree of vertex 0, excluding its self-loop, given that β and γ are constants
independent of k and β + γ > 1, is
(β + γ)k − γ k ≥ 2c log n,
∑ p0u ≥ c log n.
u∈S
8.3. Kronecker Graphs 167
Take any vertices u, v and note that puv ≥ pu0 because we have assumed that
α ≥ β ≥ γ. Therefore
To add to the picture of the structure of Gn,P[k] when β + γ > 1 we state (with-
out proof) the following result on the diameter of Gn,P[k] .
Giant Component
We now consider when Gn,P[k] has a giant component (see Horn and Radcliffe
[489]).
Theorem 8.10. Gn,P[k] has a giant component of order Θ(n) w.h.p., if and only if
(α + β )(β + γ) > 1.
Proof. We prove a weaker version of the Theorem 8.10, assuming that for α ≥
β ≥ γ as in [647]. For the proof of the more general case, see [489].
We will show first that the above condition is necessary. We prove that if
(α + β )(β + γ) ≤ 1,
(α + β )(β + γ) = 1 − ε, ε > 0.
First consider those vertices with weight (counted as the number of 1’s in their
label) less than k/2 + k2/3 and let Xu be the degree of a vertex u with weight l
where l = 0, . . . , k. It is easily observed that
E Xu = (α + β )l (β + γ)k−l . (8.19)
Hence,
l k−l
l k−l
E Xu = ∑ puv = ∑ ∑ α i β j+l−i γ k−l− j
v∈V i=0 j=0 i j
l k−l
l
=∑ α i β l−i ∑ β j γ k−l−l
i=0 i j=0
and (8.19) follows. So, if l < k/2 + k2/3 , then assuming that α ≥ β ≥ γ,
2/3 2/3
E Xu ≤(α + β )k/2+k (β + γ)k−(k/2+k )
k2/3
k/2 α + β
= ((α + β )(β + γ))
β +γ
k2/3
α +β
=(1 − ε)k/2
β +γ
=o(1). (8.20)
Suppose now that l ≥ k/2 + k2/3 and let Y be the number of 1’s in the label of
a randomly chosen vertex of Gn,P[k] . Since EY = k/2, the Chernoff bound (see
(27.26)) implies that
k 4/3 1/3
P Y ≥ +k 2/3
≤ e−k /(3k/2) ≤ e−k /2 = o(1).
2
Therefore, there are o(n) vertices with l ≥ k/2 + k2/3 . It then follows from (8.20)
that the expected number of non-isolated vertices in Gn,P[k] is o(n) and the Markov
inequality then implies that this number is o(n) w.h.p.
Next, when α + β = β + γ = 1, which implies that α = β = γ = 1/2, then
random graph Gn,P[k] is equivalent to Gn,p with p = 1/n and so by Theorem 2.21
it does not have a component of order n, w.h.p.
To prove that the condition (α + β )(β + γ) > 1 is sufficient we show that the
subgraph of Gn,P[k] induced by the vertices of H of weight l ≥ k/2 is connected
w.h.p. This will suffice as there are at least n/2 such vertices. Notice that for any
vertex u ∈ H its expected degree, by (8.19), is at least
For the given vertex u let l be the weight of u. For a vertex v let i(v) be the
number of bits where ur = vr = 1, r = 1, . . . , k, while j(v) stands for the number
of bits where ur = 0 and vr = 1. Consider the partition
V \ H = S1 ∪ S2 ∪ S3 ,
where
S1 = {v : i(v) ≥ l/2, j(v) < (k − l)/2},
S2 = {v : i(v) < l/2, j(v) ≥ (k − l)/2},
S3 = {v : i(v) < l/2, j(v) < (k − l)/2}.
Next, take a vertex v ∈ S1 and turn it into v0 by flipping the bits of v which
correspond to 0’s of u. Surely, i(v0 ) = i(v) and
Notice that the weight of v0 is at least k/2 and so v0 ∈ H. Notice also that α ≥ β ≥
γ implies that puv0 ≥ puv . Different vertices v ∈ S1 map to different v0 . Hence
The same bound (8.23) holds for S2 and S3 in place of S1 . To prove the same
relationship for S2 one has to flip the bits of v corresponding to 1’s in u, while for
S3 one has to flip all the bits of v. Adding up these bounds over the partition of
V \ H we get
∑ puv ≤ 3 ∑ puv
v∈V \H v∈H
∑ ∑ puv ≥ 10 log n.
u∈S v∈H\S
170 Chapter 8. Inhomogeneous Graphs
Without loss of generality assume that vertex 1 ∈ S. Equation (8.24) implies that
for any vertex u ∈ H either
∑ puv ≥ c log n, (8.25)
v∈S
or
∑ puv ≥ c log n. (8.26)
v∈H\S
Otherwise, (8.25) is true for every vertex u ∈ H. Since at least one such vertex is
in H \ S, we have
∑ ∑ puv ≥ c log n,
u∈S v∈H\S
8.4 Exercises
8.4.1 Prove Theorem 8.3 (with c = 10) using the result of Karger and Stein [546]
that in any
weighted graph on n vertices the number of r-minimal cuts is
O (2n)2r . (A cut (S,V \ S), S ⊆ V, in a weighted graph G is called r-
minimal if its weight, i.e., the sum of weights of the edges connecting S
with V \ S, is at most r times the weight of minimal weighted cut of G).
8.4.2 Suppose that the entries of an n×n symmetric matrix A are all non-negative.
Show that for any positive constants c1 , c2 , . . . , cn , the largest eigenvalue
λ (A) satisfies !
1 n
λ (A) ≤ max ∑ c j ai, j .
1≤i≤n ci j=1
8.4.3 Let A be the adjacency matrix of Gn,Pw and for a fixed value of x let
(
wi wi > x
ci = .
x wi ≤ x
1
Let m = max {wi : i ∈ [n]}. Let Xi = ci ∑nj=1 c j ai, j . Show that
m 2
E Xi ≤ w2 + x and Var Xi ≤ w + x.
x
8.5. Notes 171
8.4.4 Apply Theorem 27.11 with a suitable value of x to show that w.h.p.
λ (A) ≤ w2 + (6(m log n)1/2 (w2 + log n))1/2 + 3(m log n)1/2 .
8.4.5 Show that if w2 > m1/2 log n then w.h.p. λ (A) = (1 + o(1))w2 .
8.4.8 Fix d ∈ N and let Zd denote the number of vertices of degree d in the Kro-
necker random graph Gn,P[k] . Show that
k
k (α + β )dw (β + γ)d(k−w)
EZd = (1 + o(1)) ∑ ×
w=0 w d!
× exp −(α + β )w (β + γ)k−w + o(1).
8.4.9 Depending on the configuration of the parameters 0 < α, β , γ < 1, show that
we have either
k
d d
EZd = Θ (α + β ) + (β + γ) ,
or
EZd = o(2k ).
8.5 Notes
General model of inhomogeneous random graph
The most general model of inhomogeneous random graph was introduced by Bol-
lobás, Janson and Riordan in their seminal paper [168]. They concentrate on the
study of the phase transition phenomenon of their random graphs, which includes
as special cases the models presented in this chapter as well as, among others,
Dubins’ model (see Kalikow and Weiss [540] and Durrett [315]), the mean-field
scale-free model (see Riordan [761]), the CHKNS model (see Callaway, Hopcroft,
Kleinberg, Newman and Strogatz [207]) and Turova’s model (see [832], [833] and
[834]).
172 Chapter 8. Inhomogeneous Graphs
The graph Gn,m is chosen uniformly at random from the set of graphs with vertex
set [n] and m edges. It is of great interest to refine this model so that all the graphs
chosen have a fixed degree sequence d = (d1 , d2 , . . . , dn ). Of particular interest
is the case where d1 = d2 = · · · = dn = r, i.e., the graph chosen is a uniformly
random r-regular graph. It is not obvious how to do this and this is the subject of
the current chapter. We discuss the configuration model in the next section and
show its usefulness in (i) estimating the number of graphs with a given degree
sequence and (ii) showing that w.h.p. random d-regular graphs are connected
w.h.p., for 3 ≤ d = O(1).
We finish by showing in Section 9.5 how for large r, Gn,m can be embedded in
a random r-regular graph. This allows one to extend some results for Gn,m to the
regular case.
Gn,d = {simple graphs with vertex set [n] s.t. degree d(i) = di , i ∈ [n]}
11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11
00
11 00
11 00
11 00
11
11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11
00
11 00
11 00
11 00
11 00
11
00
11 00
11 00
11 00
11 00
11 00
11 00
11
11
00 11
00 11
00 11
00 11
00 11
00 11
00
00
11 00
11 00
11 00
11 00
11 00
11 00
11
11
00 11
00 11
00 11
00 11
00 11
00 11
00 11
00
00
11 00
11 00
11 00
11 00
11 00
11 00
11 00
11
00
11 00
11 00
11 00
11 00
11 00
11 00
11 00
11
1 2 3 4 5 6 7 8
00
11 00
11 00
11 00
11
11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11
00
11 00
11 00
11 00
11 00
11
11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11 11
00
00
11
11
00 11
00 11
00 11
00 11
00 11
00 11
00
00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11 00
11
00
11
00
11 00
11 00
11 00
11 00
11 00
11 00
11 11
00
11
00 11
00 11
00 11
00 11
00 11
00 11
00 00
11
00
11
00
11 00
11 00
11 00
11 00
11 00
11 00
11
1 2 3 4 5 6 7 8
2 11
00
11
00
00
11
3
11
00
00
11
00
11
111
00 4
00
11
00
11 11
00
00
11
00
11
00
11
11
00 11
00
00
11 00
11
8 00
11 5
00
11 11
00
00
11
11
00 00
11
00
11
7 6
Algorithm F-GENERATOR
begin
U ←− W, F ←− 0/
for t = 1, 2, . . . , m do
begin
Choose x arbitrarily from U;
Choose y randomly from U \ {x};
F ←− F ∪ {(x, y)};
U ←− U \ {(x, y)}
end
end
Observe that the following relationship between a simple graph G ∈ Gn,d and
the number of configurations F for which γ(F) = G.
Lemma 9.1. If G ∈ Gn,d , then
n
|γ −1 (G)| = ∏ di ! .
i=1
178 Chapter 9. Fixed Degree Sequence
Proof. Arrange the edges of G in lexicographic order. Now go through the se-
quence of 2m symbols, replacing each i by a new member of Wi . We obtain all F
for which γ(F) = G.
The above lemma implies that we can use random configurations to “approxi-
mate” random graphs with a given degree sequence.
Corollary 9.2. If F is chosen uniformly at random from the set of all configura-
tions Ω and G1 , G2 ∈ Gn,d then
P(γ(F) = G1 ) = P(γ(F) = G2 ).
So instead of sampling from the family Gn,d and counting graphs with a given
property, we can choose a random F and accept γ(F) iff there are no loops or
multiple edges, i.e. iff γ(F) is a simple graph.
This is only a useful exercise if γ(F) is simple with sufficiently high probabil-
ity. We will assume for the remainder of this section that
We will prove later (see Lemma 9.7 and Corollary 9.8) that if F is chosen
uniformly (at random) from Ω,
where
∑ di (di − 1)
λ= .
2 ∑ di
Hence, (9.1) and (9.2) will tell us not only how large is Gn,d , (Theorem 9.5)
but also lead to the following conclusion.
Theorem 9.3. Suppose that ∆ ≤ nα , α < 1/7. For any (multi)graph property P
Pr(L = 0 | Dk ⊆ F) Pr(Dk ⊆ F)
=∑ .
Dk Pr(L = 0)
Now because k = O(1), we see that the calculations that give us (9.4) will give us
Pr(L = 0 | Dk ⊆ F) ≈ Pr(L = 0). So,
D
E L = 0 ≈ ∑ Pr(Dk ⊆ F)
k Dk
d
1 2 d2i ϕ(i)
2
=
2 S,T∑ ∑ ∏ (2m − O(1))
⊆[n] ϕ:S→T i∈S
2
|S|=|T |=k
S∩T =0/
!2k
n
∆8
1 di (di − 1)
= ∑ 4m +O
k! i=1 m
180 Chapter 9. Fixed Degree Sequence
λ 2k
≈ .
k!
It follows from Theorem 26.11 that
2
Pr(D = 0 | L = 0) ≈ e−λ (9.5)
(2m)!!
|Gn,d | ≈ e−λ (λ +1) .
∏ni=1 di !
∆ k1 (d1 + · · · + dn )k1
≤ o(1) +
2m k1 !
k1
∆e
≤ o(1) +
k1
= o(1).
The o(1) term in (9.7) accounts for the probability of having a double loop.
(c)
P(F contains a pair of adjacent loops)
(d)
2 2n
di ∆
P(F contains a pair of adjacent double edges) ≤ ∑ ≤
i=1 2 2m − 8
182 Chapter 9. Fixed Degree Sequence
∆5 m
= o(1).
(2m − 8)2
(e)
3
di dj 1
P(F contains a triple edge) ≤ ∑ 6 ≤
1≤i< j≤n 3 3 2m − 6
∆5 m
= o(1).
(2m − 6)3
The o(1) term in (9.8) accounts for adjacent multiple edges and triple edges. The
∆/(2m − 4k2 ) term can be justified as follows: We have chosen two points x1 , x2
in Wa in d2i ways and this term bounds the probability that x2 chooses a partner
in the same cell as x1 .
(g)
n di 2
2 ∆ ∆3 m
E(F) ≤ ∑ ≤ ≤ ∆3 .
i=1 2m − 4 2m − 4
(i) The probability that there is an edge joining two loops is at most
n
(M1 ∆)2 ∆4
di d j (di − 2)(d j − 2)
∑ ≤ = o(1).
i6= j=1 2 2 (M1 − O(1))3 (M1 − O(1))3
Let now Ωi, j be the set of all F ∈ Ω such that F has i loops; j double edges, at
most ∆3 log n triangles and no double loops or triple edges and no vertex incident
with two double edges or with a loop and a multiple edge.
|Ω0,0 |
= (1 + o(1))e−λ (λ +1) ,
|Ω|
where
M2
λ= .
2M1
184 Chapter 9. Fixed Degree Sequence
Wa Wb Wa Wb
x1 x3 x1 x3
x2 x4 x2 x4
So,
|Ωi+2, j−1 | j
= ,
|Ωi, j | (i + 1)(i + 2)
which shows that the first statement of the Switching Lemma holds.
Wb
x3 x3
Wa
x1 x1
x2 x2
x4 x4
Wc
i M1 − 2∆2 − 2i ≤ η ≤ iM1 ,
(9.9)
(9.9). To get the lower bound we subtract the number of “bad” choices. We can
enumerate these bad choices as follows: We consider a fixed loop {x1 , x2 } con-
tained in cell Wa and we choose a pair x3 ∈ Wb and x4 ∈ Wc . The transformation
is bad only if there is x ∈ Wa \ {x1 , x2 } (≤ ∆ choices) that is paired in F with
y ∈ (Wb \ {x3 }) ∪ (Wc \ {x4 }) (≤ 2∆ choices). We also subtract 2i to account for
avoiding the other i − 1 loops in the choice of x3 , x4 .
Proof of (9.10):
In the reverse procedure, we choose a pair {x1 , x2 } ⊆ Wa in M2 /2 ways to arrive
at the upper bound. The points x3 ∈ Wb , x4 ∈ Wc are those paired with x1 , x2 in
F 0 . For the lower bound, a choice is bad only if (a, b, c) is a triangle. In this case,
we create a double edge. There are at most ∆3 log n choices for the triangle and
then three choices for a. We subtract a further i∆2 to avoid creating another loop.
Finally, we subtract i∆3 in order to avoid increasing the number of triangles by
choosing an edge that is within distance two of the loop. We also note here that
forward d-switches do not increase the number of triangles.
Now for F ∈ Ω0, j let dL (F) denote the number of F 0 ∈ Ωi−1,0 that can be
obtained from F by an `-switch. Similarly, for F 0 ∈ Ωi−1,0 let dR (F 0 ) denote the
number of F ∈ Ωi,0 that can be transformed into F 0 by an `-switch. Then,
∑ dL (F) = ∑ dR (F 0 ).
F∈Ωi,0 0
F ∈Ωi−1,0
while
M2 3 2 2 3
− 3∆ log n − 2∆ log n(∆ + ∆ ) ≤ |Ωi−1,0 | ≤
2
M2
∑ dR (F 0 ) ≤ |Ωi−1,0 |.
0
F ∈Ωi−1,0
2
So 5
|Ωi−1,0 | 2iM1 ∆ log n
= 1+O .
|Ωi,0 | M2 M1
Bollobás [146] used the configuration model to prove the following: Let Gn,r
denote a random r-regular graph with vertex set [n] and r ≥ 3 constant.
Theorem 9.9. Gn,r is r-connected, w.h.p.
Since an r-regular, r-connected graph, with n even, has a perfect matching, the
above theorem immediately implies the following Corollary.
Corollary 9.10. Let Gn,r be a random r-regular graph, r ≥ 3 constant, with vertex
set [n] even. Then w.h.p. Gn,r has a perfect matching.
Proof. (of Theorem 9.9)
Partition the vertex set V = [n] of Gn,r into three parts, K, L and V \ (K ∪ L), such
that L = N(K), i.e., such that L separates K from V \ (K ∪ L) and |L| = l ≤ r − 1.
We will show that w.h.p. there are no such K, L for k ranging from 2 to n/2. We
will use the configuration model and the relationship stated in Theorem 9.3. We
will divide the whole range of k into three parts.
(i) 2 ≤ k ≤ 3.
Put S := K ∪ L, s = |S| = k + l ≤ k + r − 1. The set S contains at least 2r − 1
edges (k = 2) or at least 3r − 3 edges (k = 3). In both cases this is at least s + 1
edges.
ne−10 r−1
r(k + l) (rk+l)/2
n n rk
P(∃K, L) ≤ ∑ ∑ rk+l
k=4 l=0 k l 2 rn
188 Chapter 9. Fixed Degree Sequence
P(∃K, L)
n n rl ϕ(rk + rl − a)ϕ(r(n − k − l) + a)
≤∑ (9.12)
k,l,a k l a ϕ(rn)
ne k ne l
≤ Cr ∑ ×
k,l,a k l
(rk + rl − a)rk+rl−a (r(n − k − l) + a)r(n−k−l)+a
(rn)rn
ne k ne l (rk)rk+rl−a (r(n − k))r(n−k−l)+a
≤ Cr0 ∑
k,l,a k l (rn)rn
ne k ne l k rk
k r(n−k)
≤ Cr00 ∑ 1−
k,l,a k l n n
9.3. Existence of a giant component 189
r−1 !k
k
≤ Cr00 ∑ e1−r/2 nr/k
k,l,a n
= o(1).
S
Explanation of (9.12): Having chosen K, L we choose a points in WK∪L = i∈K∪L Wi
that will be paired outside WK∪L . This leaves rk + rl − a points in WK∪L to be
paired up in ϕ(rk + rl − a) ways and then the remaining points can be paired up
in ϕ(r(n − k − l) + a) ways. We then multiply by the probability 1/ϕ(rn) of the
final pairing.
(a) If Λ < −ε then w.h.p. the size of the largest component in Gn,d is O(log n).
(b) If Λ > ε then w.h.p. there is a unique giant component of linear size ≈ Θn
where Θ is defined as follows: let K = ∑Li=1 iλi and
L
2α i/2
f (α) = K − 2α − ∑ iλi 1 − . (9.13)
i=1 K
L
2ψ i/2
Θ = 1 − ∑ λi 1 − .
i=1 K
(c) In Case (b), the degree sequence of the graph obtained by deleting the giant
component satisfies the conditions of (a).
(a) We fix a vertex v and estimate the size of the component containing v. We keep
track of the size of At for t = O(log n) steps. Observe that
Here M1 = ∑Li=1 iλi n as before. The explanation for (9.14) is that |A| increases
only in Step (vi) and there it increases by i − 2 with probability . Miλ1 −2t
in
. The two
points x, y are missing from At+1 and this explains the -2.
Let ε1 = ε/L and let
(
|At | + ε1t |A1 |, |A2 |, . . . , |At | > 0.
Yt =
0 Otherwise.
It follows from (9.14) that if t = O(log n) and Y1 ,Y2 , . . . ,Yt > 0 then
P(Aτ 6= 0,
/ 1 ≤ τ ≤ t) ≤ P(Yt = Z1 + Z2 + · · · + Zt > 0),
It follows that with probability 1 −O(n−2 ) that At will become empty after at most
16ε1−2 log n rounds. Thus for any fixed vertex v, with probability 1 − O(n−2 ) the
component contain v has size at most 4ε1−2 log n. (We can expose the component
containing v through our choice of x in Step (i).) Thus the probability there is a
component of size greater than 16ε1−2 log n is O(n−1 ). This completes the proof
of (a).
(b)
If t ≤ δ n for a small positive constant δ ε/L3 then
P(At 6= 0)
/ ≥ P(Yt = Z1 + Z2 + · · · + Zt > 0),
It follows that if t0 = δ n then w.h.p. |At0 | = Ω(n) and there is a giant component
and that the edges exposed between time L0 log n and time t0 are part of exactly
one giant.
We now deal with the special case where λ1 = 0. There are two cases. If in
addition we have λ2 = 1 then w.h.p. Gd is the union of O(log n) vertex disjoint
cycles, see Exercise 10.5.1. If λ1 = 0 and λ2 < 1 then the only solutions to f (α) =
0 are α = 0, K/2. For then 0 < α < K/2 implies
L
2α i/2 L
2α
∑ iλi 1 − K < ∑ iλi 1 −
K
= K − 2α.
i=2 i=2
This gives Θ = 1. Exercise 10.5.2 asks for a proof that w.h.p. in this case, Gn,d
consists a giant component plus a collection of small components that are cycles
of size O(log n).
Assume now then that λ1 > 0. We show that w.h.p. there are Ω(n) isolated
edges. This together with the rest of the proof implies that Ψ < K/2 and hence
that Θ < 1. Indeed, if Z denotes the number components that are isolated edges,
then
λ1 n 1 λ1 n 6
E(Z) = and E(Z(Z − 1)) =
2 2M1 − 1 4 (2M1 − 1)(2M1 − 3)
2τ i/2
x = λi 1 − . (9.18)
K
In what follows, we use the notation of Section 28, except that we replace λ0
by ξ0 = n−1/4 to avoid confusion with λi .
(P0) D = (τ, x) : 0 < τ < Θ−ε
2 , 2ξ0 < x < 1 where ε is small and positive.
(P1) C0 = 1.
(P2) β = L.
ix
(P3) f (τ, x) = − K−2τ and γ = 0.
(P4) The Lipschitz constant L1 = 2K/(K − 2Θ)2 . This needs justification and
follows from
x x0 K(x − x0 ) + 2τ(x − x0 ) + 2x(τ − τ 0 )
− = .
K − 2τ K − 2τ 0 (K − 2τ)(K − 2τ 0 )
1/4 )
Theorem 28.1 then implies that with probability 1 − O(n1/4 e−Ω(n ),
2t i/2
Xi,t − niλi 1 − = O(n3/4 ), (9.19)
K
up to a point where Xi,t = O(ξ0 n). (The o(n3/4 ) term for the number of vertices
of degree i is absorbed into the RHS of (9.19).)
Now because
L L
|At | = M1 − 2t − ∑ iXi,t = Kn − 2t − ∑ iXi,t ,
i=1 i=1
2Ψ i/2
0
λi = λi 1 − .
K
(The important thing here is that the number of vertices of degree i is asymptot-
ically proportional to λi0 .) Next choose ε1 > 0 sufficiently small and let tε1 =
max {t : |At | ≥ ε1 n}. There must exist ε2 < ε1 such that tε1 ≤ (Ψ − ε2 )n and
f 0 (Ψ − ε2 ) ≤ −ε1 , else f cannot reach zero. Recall that Ψ < K/2 here and then,
2Ψ − 2ε2 i/2
0 1 2
−ε1 ≥ f (Ψ − ε2 ) = −2 + ∑ i λi 1 − K
K − 2(Ψ − ε2 ) i≥1
2Ψ i/2
1 + O(ε2 ) 2
= −2 + ∑ i λi 1 − K
K − 2Ψ i≥1
i/2 !
2Ψ i/2
1 + O(ε2 ) 2Ψ
= −2 ∑ iλi 1 − + ∑ i2 λi 1 −
K − 2Ψ i≥1 K i≥1 K
2Ψ i/2
1 + O(ε2 )
=
K − 2Ψ i≥1∑ i(i − 2)λi 1 − K
1 + O(ε2 )
=
K − 2Ψ i≥1∑ i(i − 2)λi0. (9.21)
Lemma 9.12.
Let `0 = 100 logr−1 log n . Then w.h.p., eG (S) ≤ |S| for all S ⊆ [n], |S| ≤ 2`0 .
Proof. Arguing as for (9.11), we have that
2`0 s+1
n sr sr
P(∃S : |S| ≤ 2`0 , eG (S) ≥ |S| + 1) ≤ ∑
s=4 s s+1 rn − 4`0
2`0 s+1
ne s s+1 s
≤∑ (er)
s=4 s n − o(n)
1 2`0 2s+1+o(1)
≤ ∑ se = o(1).
n s=4
Let E denote the high probability event in Lemma 9.12. We will condition on
the occurence of E .
Now for v ∈ [n] let Sk (v) denote the set of vertices at distance k from v and let
S
S≤k (v) = j≤k S j (v). We note that
Proof. The probability that the kth edge is dispensable is at most (k−1)r
rn−2k , indepen-
dent of the history of the process. Hence,
2/5 !20
n rn2/5
P(∃ 20 dispensable edges in first n2/5 ) ≤ = o(n−2 ).
20 rn − o(n)
196 Chapter 9. Fixed Degree Sequence
3/5 !n1/4
n rn3/5
1/4 3/5
P(∃ n dispensable edges in first n ) ≤ 1/4 = o(n−2 ).
n rn − o(n)
l m l m
Now let `1 = logr−1 n2/5 and `2 = logr−1 n3/5 . Then we have that, con-
ditional on E , with probability 1 − o(n−2 ),
|Sk (w)| ≥ ((r − 2)(r + 1) − o(1))(r − 1)k−2 ≈ (r − 2)(r + 1)(r − 1)a−2 n4/7 .
|Sk (w) \ Sk (v)| ≥ (r − 2 − o(1))(r − 1)k−1 ≈ (r − 2)(r − 1)a−1 n4/7 .
Suppose now that we consider the execution of breadth first search up until we
have determined Sk (v), but we have only determined Sk−1 (w). When we expose
the unused edges of Sk−1 (w), some of these pairings will fall in S≤k (v) ∪ Sk−1 (w).
Expose any such pairings and condition on the outcome. There are at most n1/4
such pairings and the size of |Sk (v) ∩ Sk (w)| is now determined. Then in order to
have dk (v) = dk (w) there has to be an exact outcome t for |Sk (w) \ Sk (v)|. There
must now be s = Θ(n4/7 ) pairings between Wx , x ∈ Sk−1 (w) and Wy , y ∈ / S≤k (v) ∪
Sk−1 (w). Furthermore, to have dk (v) = dk (w) these s pairings must involve exactly
t of the sets Wy , y ∈
/ Sk (v) ∪ Sk (w), where t is determined before the choice of these
s pairings. The following lemma will then be used to show that G is asymmetric
w.h.p.
c0 m1/2
max P(XS = j) ≤ ,
j s
Proof. We may assume that s ≥ m1/2 . The probability that S has at least 3 ele-
ments in some set Ri is at most
m 3r rm−3
s−3 s3 m1/2
rm ≤ ≤ .
s
m2 s
But
P(XS = j) ≤ P max |S ∩ Ri | ≥ 3 + P XS = j and max |S ∩ Ri | ≤ 2 .
i i
c1 m1/2
Pj = P XS = j and max |S ∩ Ri | ≤ 2 ≤ , (9.25)
i s
Pj+1 (m − j)(s − j) 2r
= . (9.27)
Pj (2 j + 2 − s)(2 j + 1 − s) r − 1
(r − 1)s2
j0 − s − ≤ 1.
2rm
s
Furthermore, if j1 = j0 − m1/2 then
Pj+1 m1/2
≤ 1 + c3 for j1 ≤ j ≤ j0 ,
Pj s
198 Chapter 9. Fixed Degree Sequence
This proves
Theorem 9.15. W.h.p. Gn,r has a unique trivial automorphism.
r log n 1/3
C + ≤ γ = γ(n) < 1,
n r
and m = b(1 − γ)nr/2c, then there is a joint distribution of G(n, m) and Gn,r such
that
P(Gn,m ⊂ Gn,r ) → 1.
9.5. Gn,r versus Gn,p 199
Corollary 9.17. Let Q be an increasing property of graphs such that Gn,m satis-
fies Q w.h.p. for some m = m(n), n log n m n2 . Then Gn,r satisfies Q w.h.p.
for r = r(n) ≈ 2m
n .
Our approach to proving Theorem 9.16 is to represent Gn,m and Gn,r as the
outcomes of two graph processes which behave similarly enough to permit a good
coupling. For this let M = nr/2 and define
GM = (ε1 , . . . , εM )
to be an ordered random uniform graph on the vertex set [n], that is, Gn,M with a
random uniform ordering of edges. Similarly, let
Gr = (η1 , . . . , ηM )
be an ordered random r-regular graph on [n], that is, Gn,r with a random uniform
ordering of edges. Further, write GM (t) = (ε1 , . . . , εt ) and Gr (t) = (η1 , . . . , ηt ),
t = 0, . . . , M.
For every ordered graph G of size t and every edge e ∈ Kn \ G we have
1
Pr (εt+1 = e | GM (t) = G) = n .
2 −t
This is not true if we replace GM by Gr , except for the very first step t = 0.
However, it turns out that for most of time the conditional distribution of the next
edge in the process Gr (t) is approximately uniform, which is made precise in the
lemma below. For 0 < ε < 1, and t = 0, . . . , M consider the inequalities
1−ε
Pr (ηt+1 = e | Gr (t)) ≥ n for every e ∈ Kn \ Gr (t), (9.28)
2 − t
Proof of Theorem 9.16. Let C = 3C0 , where C0 is the constant from Lemma 9.18.
Let ε = γ/3. The distribution of Gr is uniquely determined by the conditional
probabilities
Our aim is to couple GM and Gr up to the time Tε . For this we will define a
graph process G0r := (ηt0 ),t = 1, . . . , M such that the conditional distribution of
(ηt0 ) coincides with that of (ηt ) and w.h.p. (ηt0 ) shares many edges with GM .
Suppose that Gr = G0r (t) and GM = GM (t) have been exposed and for every
e∈/ Gr the inequality
1−ε
pt+1 (e|Gr ) ≥ n (9.31)
2 −t
holds (we have such a situation, in particular, if t ≤ Tε ). Generate a Bernoulli
(1 − ε) random variable ξt+1 independently of everything that has been revealed
so far; expose the edge εt+1 . Moreover, generate a random edge ζt+1 ∈ Kn \ Gr
according to the distribution
1−ε
pt+1 (e|Gr ) −
(n2)−t
P(ζt+1 = e|G0r (t) = Gr , GM (t) = GM ) := ≥ 0,
ε
where the inequality holds because of the assumption (9.31). Observe also that
Note that
ξt+1 = 1 ⇒ εt+1 ∈ G0r (t + 1). (9.32)
We keep generating ξt ’s even after the stopping time has passed, that is, for t > Tε ,
0
whereas ηt+1 is then sampled according to probabilities (9.30), without coupling.
Note that ξt ’s are i.i.d. and independent of GM . We check that
0
P(ηt+1 = e | G0r (t) = Gr , GM (t) = GM )
= P(εt+1 = e) P(ξt+1 = 1) + P(ζt+1 = e) P(ξt+1 = 0)
9.5. Gn,r versus Gn,p 201
1−ε
pt+1 (e|Gr ) −
1−ε (n2)−t
= n + ε
2 − t ε
= pt+1 (e|Gr )
for all admissible Gr , GM , i.e., such that P (Gr (t) = Gr , GM (t) = GM ) > 0, and
for all e 6∈ Gr .
Further, define a set of edges which are potentially shared by GM and Gr :
S := {εi : ξi = 1 , 1 ≤ i ≤ (1 − ε)M} .
Note that
b(1−ε)Mc
|S| = ∑ ξi
i=1
is distributed as Bin(b(1 − ε)Mc, 1 − ε).
Since (ξi ) and (εi ) are independent, conditioning on |S| ≥ m, the first m edges
in the set S comprise a graph which is distributed as Gn,m . Moreover, if Tε ≥
(1 − ε)M, then by (9.32) we have S ⊂ Gr , therefore
P (Gn,m ⊂ Gn,r ) ≥ P (|S| ≥ m, Tε ≥ (1 − ε)M) .
We have E |S| ≥ (1 − 2ε)M. Recall that ε = γ/3 and therefore m = b(1 − γ)Mc =
b(1 − 3ε)Mc. Applying the Chernoff bounds and our assumption on ε, we get
2 m)
P (|S| < m) ≤ e−Ω(γ = o(1).
Finally, by Lemma 9.18 we have Tε ≥ (1 − ε)M w.h.p., which completes the proof
of the theorem.
x2
P (|X − tr/M| ≥ x) ≤ 2 exp − .
2 (τr + x/3)
√
Let x = 6 τr log n. From (9.29), assuming C0 ≥ 1, we get
r r
x log n log n
=6 ≤6 ≤ 6ε,
τr τr εr
and so x ≤ 6τr. Using this, we obtain
1 36τr log n
P (|X − tr/M| ≥ x) ≤ exp − = n−6 .
2 2(τr + 2τr)
or, equivalently, ε ≥ 144 log n/r, which is implied by (9.29) with C0 ≥ 144.
Given an ordered graph G = (e1 , . . . , et ), we say that an ordered r-regular graph
H is an extension of G if the first t edges of H are equal to G. Let GG (n, r) be the
family of extensions of G and GG = GG (n, r) be a graph chosen uniformly at
random from GG (n, r).
Further, for a graph H ∈ GG (n, r) and u, v ∈ [n] let
Note that degH|G (u, v) is not in general symmetric in u and v, but for G = 0/ coin-
cides with the usual co-degree in a graph H.
The next fact is used in the proof of Lemma 9.21 only.
Lemma 9.20. Let graph G with t ≤ (1 − ε)M edges be such that GG (n, r) is
nonempty. For each e ∈
/ G we have
4r
P (e ∈ GG ) ≤ . (9.35)
εn
9.5. Gn,r versus Gn,p 203
Let us define an auxiliary bipartite graph B between Ge∈ and Ge∈/ in which H ∈ Ge∈
is connected to H 0 ∈ Ge∈/ whenever H 0 can be obtained