# Erdős–Rényi Random Graphs

Consider a graph ${\displaystyle G(V,E)}$ which is randomly generated as:

• ${\displaystyle |V|=n}$;
• ${\displaystyle \forall \{u,v\}\in {V \choose 2}}$, ${\displaystyle uv\in E}$ independently with probability ${\displaystyle p}$.

Such graph is denoted as ${\displaystyle G(n,p)}$. This is called the Erdős–Rényi model or ${\displaystyle G(n,p)}$ model for random graphs.

Informally, the presence of every edge of ${\displaystyle G(n,p)}$ is determined by an independent coin flipping (with probability of HEADs ${\displaystyle p}$).

# Monotone properties

A graph property is a predicate of graph which depends only on the structure of the graph.

 Definition Let ${\displaystyle {\mathcal {G}}_{n}=2^{V \choose 2}}$, where ${\displaystyle |V|=n}$, be the set of all possible graphs on ${\displaystyle n}$ vertices. A graph property is a boolean function ${\displaystyle P:{\mathcal {G}}_{n}\rightarrow \{0,1\}}$ which is invariant under permutation of vertices, i.e. ${\displaystyle P(G)=P(H)}$ whenever ${\displaystyle G}$ is isomorphic to ${\displaystyle H}$.

We are interested in the monotone properties, i.e., those properties that adding edges will not change a graph from having the property to not having the property.

 Definition A graph property ${\displaystyle P}$ is monotone if for any ${\displaystyle G\subseteq H}$, both on ${\displaystyle n}$ vertices, ${\displaystyle G}$ having property ${\displaystyle P}$ implies ${\displaystyle H}$ having property ${\displaystyle P}$.

By seeing the property as a function mapping a set of edges to a numerical value in ${\displaystyle \{0,1\}}$, a monotone property is just a monotonically increasing set function.

Some examples of monotone graph properties:

• Hamiltonian;
• ${\displaystyle k}$-clique;
• contains a subgraph isomorphic to some ${\displaystyle H}$;
• non-planar;
• chromatic number ${\displaystyle >k}$ (i.e., not ${\displaystyle k}$-colorable);
• girth ${\displaystyle <\ell }$.

From the last two properties, you can see another reason that the Erdős theorem is unintuitive.

Some examples of non-monotone graph properties:

• Eulerian;
• contains an induced subgraph isomorphic to some ${\displaystyle H}$;

For all monotone graph properties, we have the following theorem.

 Theorem Let ${\displaystyle P}$ be a monotone graph property. Suppose ${\displaystyle G_{1}=G(n,p_{1})}$, ${\displaystyle G_{2}=G(n,p_{2})}$, and ${\displaystyle 0\leq p_{1}\leq p_{2}\leq 1}$. Then ${\displaystyle \Pr[P(G_{1})]\leq \Pr[P(G_{2})]}$.

Although the statement in the theorem looks very natural, it is difficult to evaluate the probability that a random graph has some property. However, the theorem can be very easily proved by using the idea of coupling, a proof technique in probability theory which compare two unrelated random variables by forcing them to be related.

Proof.
 For any ${\displaystyle \{u,v\}\in {[n] \choose 2}}$, let ${\displaystyle X_{\{u,v\}}}$ be independently and uniformly distributed over the continuous interval ${\displaystyle [0,1]}$. Let ${\displaystyle uv\in G_{1}}$ if and only if ${\displaystyle X_{\{u,v\}}\in [0,p_{1}]}$ and let ${\displaystyle uv\in G_{2}}$ if and only if ${\displaystyle X_{\{u,v\}}\in [0,p_{2}]}$. It is obvious that ${\displaystyle G_{1}\sim G(n,p_{1})\,}$ and ${\displaystyle G_{2}\sim G(n,p_{2})\,}$. For any ${\displaystyle \{u,v\}}$, ${\displaystyle uv\in G_{1}}$ means that ${\displaystyle X_{\{u,v\}}\in [0,p_{1}]\subseteq [0,p_{2}]}$, which implies that ${\displaystyle uv\in G_{2}}$. Thus, ${\displaystyle G_{1}\subseteq G_{2}}$. Since ${\displaystyle P}$ is monotone, ${\displaystyle P(G_{1})=1}$ implies ${\displaystyle P(G_{2})}$. Thus, ${\displaystyle \Pr[P(G_{1})=1]\leq \Pr[P(G_{2})=1]}$.
${\displaystyle \square }$

# Threshold phenomenon

One of the most fascinating phenomenon of random graphs is that for so many natural graph properties, the random graph ${\displaystyle G(n,p)}$ suddenly changes from almost always not having the property to almost always having the property as ${\displaystyle p}$ grows in a very small range.

A monotone graph property ${\displaystyle P}$ is said to have the threshold ${\displaystyle p(n)}$ if

• when ${\displaystyle p\ll p(n)}$, ${\displaystyle \Pr[P(G(n,p))]=0}$ as ${\displaystyle n\rightarrow \infty }$ (also called ${\displaystyle G(n,p)}$ almost always does not have ${\displaystyle P}$); and
• when ${\displaystyle p\gg p(n)}$, ${\displaystyle \Pr[P(G(n,p))]=1}$ as ${\displaystyle n\rightarrow \infty }$ (also called ${\displaystyle G(n,p)}$ almost always has ${\displaystyle P}$).

The classic method for proving the threshold is the so-called second moment method (Chebyshev's inequality).

 Theorem The threshold for a random graph ${\displaystyle G(n,p)}$ to contain a 4-clique is ${\displaystyle p=n^{2/3}}$.

We formulate the problem as such. For any ${\displaystyle 4}$-subset of vertices ${\displaystyle S\in {V \choose 4}}$, let ${\displaystyle X_{S}}$ be the indicator random variable such that

${\displaystyle X_{S}={\begin{cases}1&S{\mbox{ is a clique}},\\0&{\mbox{otherwise}}.\end{cases}}}$

Let ${\displaystyle X=\sum _{S\in {V \choose 4}}X_{S}}$ be the total number of 4-cliques in ${\displaystyle G}$.

It is sufficient to prove the following lemma.

 Lemma If ${\displaystyle p=o(n^{-2/3})}$, then ${\displaystyle \Pr[X\geq 1]\rightarrow 0}$ as ${\displaystyle n\rightarrow \infty }$. If ${\displaystyle p=\omega (n^{-2/3})}$, then ${\displaystyle \Pr[X\geq 1]\rightarrow 1}$ as ${\displaystyle n\rightarrow \infty }$.
Proof.
 The first claim is proved by the first moment (expectation and Markov's inequality) and the second claim is proved by the second moment method (Chebyshev's inequality). Every 4-clique has 6 edges, thus for any ${\displaystyle S\in {V \choose 4}}$, ${\displaystyle \mathbf {E} [X_{S}]=\Pr[X_{S}=1]=p^{6}}$. By the linearity of expectation, ${\displaystyle \mathbf {E} [X]=\sum _{S\in {V \choose 4}}\mathbf {E} [X_{S}]={n \choose 4}p^{6}}$. Applying Markov's inequality ${\displaystyle \Pr[X\geq 1]\leq \mathbf {E} [X]=O(n^{4}p^{6})=o(1)}$, if ${\displaystyle p=o(n^{-2/3})}$. The first claim is proved. To prove the second claim, it is equivalent to show that ${\displaystyle \Pr[X=0]=o(1)}$ if ${\displaystyle p=\omega (n^{-2/3})}$. By the Chebyshev's inequality, ${\displaystyle \Pr[X=0]\leq \Pr[|X-\mathbf {E} [X]|\geq \mathbf {E} [X]]\leq {\frac {\mathbf {Var} [X]}{(\mathbf {E} [X])^{2}}}}$, where the variance is computed as ${\displaystyle \mathbf {Var} [X]=\mathbf {Var} \left[\sum _{S\in {V \choose 4}}X_{S}\right]=\sum _{S\in {V \choose 4}}\mathbf {Var} [X_{S}]+\sum _{S,T\in {V \choose 4},S\neq T}\mathbf {Cov} (X_{S},X_{T})}$. For any ${\displaystyle S\in {V \choose 4}}$, ${\displaystyle \mathbf {Var} [X_{S}]=\mathbf {E} [X_{S}^{2}]-\mathbf {E} [X_{S}]^{2}\leq \mathbf {E} [X_{S}^{2}]=\mathbf {E} [X_{S}]=p^{6}}$. Thus the first term of above formula is ${\displaystyle \sum _{S\in {V \choose 4}}\mathbf {Var} [X_{S}]=O(n^{4}p^{6})}$. We now compute the covariances. For any ${\displaystyle S,T\in {V \choose 4}}$ that ${\displaystyle S\neq T}$: Case.1: ${\displaystyle |S\cap T|\leq 1}$, so ${\displaystyle S}$ and ${\displaystyle T}$ do not share any edges. ${\displaystyle X_{S}}$ and ${\displaystyle X_{T}}$ are independent, thus ${\displaystyle \mathbf {Cov} (X_{S},X_{T})=0}$. Case.2: ${\displaystyle |S\cap T|=2}$, so ${\displaystyle S}$ and ${\displaystyle T}$ share an edge. Since ${\displaystyle |S\cup T|=6}$, there are ${\displaystyle {n \choose 6}=O(n^{6})}$ pairs of such ${\displaystyle S}$ and ${\displaystyle T}$. ${\displaystyle \mathbf {Cov} (X_{S},X_{T})=\mathbf {E} [X_{S}X_{T}]-\mathbf {E} [X_{S}]\mathbf {E} [X_{T}]\leq \mathbf {E} [X_{S}X_{T}]=\Pr[X_{S}=1\wedge X_{T}=1]=p^{11}}$ since there are 11 edges in the union of two 4-cliques that share a common edge. The contribution of these pairs is ${\displaystyle O(n^{6}p^{11})}$. Case.2: ${\displaystyle |S\cap T|=3}$, so ${\displaystyle S}$ and ${\displaystyle T}$ share a triangle. Since ${\displaystyle |S\cup T|=5}$, there are ${\displaystyle {n \choose 5}=O(n^{5})}$ pairs of such ${\displaystyle S}$ and ${\displaystyle T}$. By the same argument, ${\displaystyle \mathbf {Cov} (X_{S},X_{T})\leq \Pr[X_{S}=1\wedge X_{T}=1]=p^{9}}$ since there are 9 edges in the union of two 4-cliques that share a triangle. The contribution of these pairs is ${\displaystyle O(n^{5}p^{9})}$. Putting all these together, ${\displaystyle \mathbf {Var} [X]=O(n^{4}p^{6}+n^{6}p^{11}+n^{5}p^{9}).}$ And ${\displaystyle \Pr[X=0]\leq {\frac {\mathbf {Var} [X]}{(\mathbf {E} [X])^{2}}}=O(n^{-4}p^{-6}+n^{-2}p^{-1}+n^{-3}p^{-3})}$, which is ${\displaystyle o(1)}$ if ${\displaystyle p=\omega (n^{-2/3})}$. The second claim is also proved.
${\displaystyle \square }$

The above theorem can be generalized to any "balanced" subgraphs.

 Definition The density of a graph ${\displaystyle G(V,E)}$, denoted ${\displaystyle \rho (G)\,}$, is defined as ${\displaystyle \rho (G)={\frac {|E|}{|V|}}}$. A graph ${\displaystyle G(V,E)}$ is balanced if ${\displaystyle \rho (H)\leq \rho (G)}$ for all subgraphs ${\displaystyle H}$ of ${\displaystyle G}$.

Cliques are balanced, because ${\displaystyle {\frac {k \choose 2}{k}}\leq {\frac {n \choose 2}{n}}}$ for any ${\displaystyle k\leq n}$. The threshold for 4-clique is a direct corollary of the following general theorem.

 Theorem (Erdős–Rényi 1960) Let ${\displaystyle H}$ be a balanced graph with ${\displaystyle k}$ vertices and ${\displaystyle \ell }$ edges. The threshold for the property that a random graph ${\displaystyle G(n,p)}$ contains a (not necessarily induced) subgraph isomorphic to ${\displaystyle H}$ is ${\displaystyle p=n^{-k/\ell }\,}$.
Sketch of proof.
 For any ${\displaystyle S\in {V \choose k}}$, let ${\displaystyle X_{S}}$ indicate whether ${\displaystyle G_{S}}$ (the subgraph of ${\displaystyle G}$ induced by ${\displaystyle S}$) contain a subgraph ${\displaystyle H}$. Then ${\displaystyle p^{\ell }\leq \mathbf {E} [X_{S}]\leq k!p^{\ell }}$, since there are at most ${\displaystyle k!}$ ways to match the substructure. Note that ${\displaystyle k}$ does not depend on ${\displaystyle n}$. Thus, ${\displaystyle \mathbf {E} [X_{S}]=\Theta (p^{\ell })}$. Let ${\displaystyle X=\sum _{S\in {V \choose k}}X_{S}}$ be the number of ${\displaystyle H}$-subgraphs. ${\displaystyle \mathbf {E} [X]=\Theta (n^{k}p^{\ell })}$. By Markov's inequality, ${\displaystyle \Pr[X\geq 1]\leq \mathbf {E} [X]=\Theta (n^{k}p^{\ell })}$ which is ${\displaystyle o(1)}$ when ${\displaystyle p\ll n^{-\ell /k}}$. By Chebyshev's inequality, ${\displaystyle \Pr[X=0]\leq {\frac {\mathbf {Var} [X]}{\mathbf {E} [X]^{2}}}}$ where ${\displaystyle \mathbf {Var} [X]=\sum _{S\in {V \choose k}}\mathbf {Var} [X_{S}]+\sum _{S\neq T}\mathbf {Cov} (X_{S},X_{T})}$. The first term ${\displaystyle \sum _{S\in {V \choose k}}\mathbf {Var} [X_{S}]\leq \sum _{S\in {V \choose k}}\mathbf {E} [X_{S}^{2}]=\sum _{S\in {V \choose k}}\mathbf {E} [X_{S}]=\mathbf {E} [X]=\Theta (n^{k}p^{\ell })}$. For the covariances, ${\displaystyle \mathbf {Cov} (X_{S},X_{T})\neq 0}$ only if ${\displaystyle |S\cap T|=i}$ for ${\displaystyle 2\leq i\leq k-1}$. Note that ${\displaystyle |S\cap T|=i}$ implies that ${\displaystyle |S\cup T|=2k-i}$. And for balanced ${\displaystyle H}$, the number of edges of interest in ${\displaystyle S}$ and ${\displaystyle T}$ is ${\displaystyle 2\ell -i\rho (H_{S\cap T})\geq 2\ell -i\rho (H)=2\ell -i\ell /k}$. Thus, ${\displaystyle \mathbf {Cov} (X_{S},X_{T})\leq \mathbf {E} [X_{S}X_{T}]\leq p^{2\ell -i\ell /k}}$. And, ${\displaystyle \sum _{S\neq T}\mathbf {Cov} (X_{S},X_{T})=\sum _{i=2}^{k-1}O(n^{2k-i}p^{2\ell -i\ell /k})}$ Therefore, when ${\displaystyle p\gg n^{-\ell /k}}$, ${\displaystyle \Pr[X=0]\leq {\frac {\mathbf {Var} [X]}{\mathbf {E} [X]^{2}}}\leq {\frac {\Theta (n^{k}p^{\ell })+\sum _{i=2}^{k-1}O(n^{2k-i}p^{2\ell -i\ell /k})}{\Theta (n^{2k}p^{2\ell })}}=\Theta (n^{-k}p^{-\ell })+\sum _{i=2}^{k-1}O(n^{-i}p^{-i\ell /k})=o(1)}$.
${\displaystyle \square }$