# 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}$).

# 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).

## Threshold for 4-clique

 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 }$

## Threshold for balanced subgraphs

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 }$

# Two-point sampling

## Pairwise Independent Variables

We now consider constructing pairwise independent random variables ranging over ${\displaystyle [p]=\{0,1,2,\ldots ,p-1\}}$ for some prime ${\displaystyle p}$. We assume ${\displaystyle X_{0},X_{1}}$ to be two independent random variables which are uniformly and independently distributed over ${\displaystyle [p]}$.

Let ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{p-1}}$ be defined as:

{\displaystyle {\begin{aligned}Y_{i}=(X_{0}+i\cdot X_{1}){\bmod {p}}&\quad {\mbox{for }}i\in [p].\end{aligned}}}
 Theorem The random variables ${\displaystyle Y_{0},Y_{1},\ldots ,Y_{p-1}}$ are pairwise independent uniform random variables over ${\displaystyle [p]}$.
Proof.
 We first show that ${\displaystyle Y_{i}}$ are uniform. That is, we will show that for any ${\displaystyle i,a\in [p]}$, {\displaystyle {\begin{aligned}\Pr \left[(X_{0}+i\cdot X_{1}){\bmod {p}}=a\right]&={\frac {1}{p}}.\end{aligned}}} Due to the law of total probability, {\displaystyle {\begin{aligned}\Pr \left[(X_{0}+i\cdot X_{1}){\bmod {p}}=a\right]&=\sum _{j\in [p]}\Pr[X_{1}=j]\cdot \Pr \left[(X_{0}+ij){\bmod {p}}=a\right]\\&={\frac {1}{p}}\sum _{j\in [p]}\Pr \left[X_{0}\equiv (a-ij){\pmod {p}}\right].\end{aligned}}} For prime ${\displaystyle p}$, for any ${\displaystyle i,j,a\in [p]}$, there is exact one value in ${\displaystyle [p]}$ of ${\displaystyle X_{0}}$ satisfying ${\displaystyle X_{0}\equiv (a-ij){\pmod {p}}}$. Thus, ${\displaystyle \Pr \left[X_{0}\equiv (a-ij){\pmod {p}}\right]=1/p}$ and the above probability is ${\displaystyle {\frac {1}{p}}}$. We then show that ${\displaystyle Y_{i}}$ are pairwise independent, i.e. we will show that for any ${\displaystyle Y_{i},Y_{j}}$ that ${\displaystyle i\neq j}$ and any ${\displaystyle a,b\in [p]}$, {\displaystyle {\begin{aligned}\Pr \left[Y_{i}=a\wedge Y_{j}=b\right]&={\frac {1}{p^{2}}}.\end{aligned}}} The event ${\displaystyle Y_{i}=a\wedge Y_{j}=b}$ is equivalent to that ${\displaystyle {\begin{cases}(X_{0}+iX_{1})\equiv a{\pmod {p}}\\(X_{0}+jX_{1})\equiv b{\pmod {p}}\end{cases}}}$ Due to the Chinese remainder theorem, there exists a unique solution of ${\displaystyle X_{0}}$ and ${\displaystyle X_{1}}$ in ${\displaystyle [p]}$ to the above linear congruential system. Thus the probability of the event is ${\displaystyle {\frac {1}{p^{2}}}}$.
${\displaystyle \square }$

## Two-spoint sampling

Consider a Monte Carlo randomized algorithm with one-sided error for a decision problem ${\displaystyle f}$. We formulate the algorithm as a deterministic algorithm ${\displaystyle A}$ that takes as input ${\displaystyle x}$ and a uniform random number ${\displaystyle r\in [p]}$ where ${\displaystyle p}$ is a prime, such that for any input ${\displaystyle x}$:

• If ${\displaystyle f(x)=1}$, then ${\displaystyle \Pr[A(x,r)=1]\geq {\frac {1}{2}}}$, where the probability is taken over the random choice of ${\displaystyle r}$.
• If ${\displaystyle f(x)=0}$, then ${\displaystyle A(x,r)=0}$ for any ${\displaystyle r}$.

We call ${\displaystyle r}$ the random source for the algorithm.

For the ${\displaystyle x}$ that ${\displaystyle f(x)=1}$, we call the ${\displaystyle r}$ that makes ${\displaystyle A(x,r)=1}$ a witness for ${\displaystyle x}$. For a positive ${\displaystyle x}$, at least half of ${\displaystyle [p]}$ are witnesses. The random source ${\displaystyle r}$ has polynomial number of bits, which means that ${\displaystyle p}$ is exponentially large, thus it is infeasible to find the witness for an input ${\displaystyle x}$ by exhaustive search. Deterministic overcomes this by having sophisticated deterministic rules for efficiently searching for a witness. Randomization, on the other hard, reduce this to a bit of luck, by randomly choosing an ${\displaystyle r}$ and winning with a probability of 1/2.

We can boost the accuracy (equivalently, reduce the error) of any Monte Carlo randomized algorithm with one-sided error by running the algorithm for a number of times.

Suppose that we sample ${\displaystyle t}$ values ${\displaystyle r_{1},r_{2},\ldots ,r_{t}}$ uniformly and independently from ${\displaystyle [p]}$, and run the following scheme:

 ${\displaystyle B(x,r_{1},r_{2},\ldots ,r_{t}):}$ return ${\displaystyle \bigvee _{i=1}^{t}A(x,r_{i})}$;

That is, return 1 if any instance of ${\displaystyle A(x,r_{i})=1}$. For any ${\displaystyle x}$ that ${\displaystyle f(x)=1}$, due to the independence of ${\displaystyle r_{1},r_{2},\ldots ,r_{t}}$, the probability that ${\displaystyle B(x,r_{1},r_{2},\ldots ,r_{t})}$ returns an incorrect result is at most ${\displaystyle 2^{-t}}$. On the other hand, ${\displaystyle B}$ never makes mistakes for the ${\displaystyle x}$ that ${\displaystyle f(x)=0}$ since ${\displaystyle A}$ has no false positives. Thus, the error of the Monte Carlo algorithm is reduced to ${\displaystyle 2^{-t}}$.

Sampling ${\displaystyle t}$ mutually independent random numbers from ${\displaystyle [p]}$ can be quite expensive since it requires ${\displaystyle \Omega (t\log p)}$ random bits. Suppose that we can only afford ${\displaystyle O(\log p)}$ random bits. In particular, we sample two independent uniform random number ${\displaystyle a}$ and ${\displaystyle b}$ from ${\displaystyle [p]}$. If we use ${\displaystyle a}$ and ${\displaystyle b}$ directly bu running two independent instances ${\displaystyle A(x,a)}$ and ${\displaystyle A(x,b)}$, we only get an error upper bound of 1/4.

The following scheme reduces the error significantly with the same number of random bits:

 Algorithm Choose two independent uniform random number ${\displaystyle a}$ and ${\displaystyle b}$ from ${\displaystyle [p]}$. Construct ${\displaystyle t}$ random number ${\displaystyle r_{1},r_{2},\ldots ,r_{t}}$ by: {\displaystyle {\begin{aligned}\forall 1\leq i\leq t,&\quad {\mbox{let }}r_{i}=(a\cdot i+b){\bmod {p}}.\end{aligned}}} Run ${\displaystyle B(x,r_{1},r_{2},\ldots ,r_{t}):}$.

Due to the discussion in the last section, we know that for ${\displaystyle t\leq p}$, ${\displaystyle r_{1},r_{2},\ldots ,r_{t}}$ are pairwise independent and uniform over ${\displaystyle [p]}$. Let ${\displaystyle X_{i}=A(x,r_{i})}$ and ${\displaystyle X=\sum _{i=1}^{t}X_{i}}$. Due to the uniformity of ${\displaystyle r_{i}}$ and our definition of ${\displaystyle A}$, for any ${\displaystyle x}$ that ${\displaystyle f(x)=1}$, it holds that

${\displaystyle \Pr[X_{i}=1]=\Pr[A(x,r_{i})=1]\geq {\frac {1}{2}}.}$

By the linearity of expectations,

${\displaystyle \mathbf {E} [X]=\sum _{i=1}^{t}\mathbf {E} [X_{i}]=\sum _{i=1}^{t}\Pr[X_{i}=1]\geq {\frac {t}{2}}.}$

Since ${\displaystyle X_{i}}$ is Bernoulli trial with a probability of success at least ${\displaystyle p=1/2}$. We can estimate the variance of each ${\displaystyle X_{i}}$ as follows.

${\displaystyle \mathbf {Var} [X_{i}]=p(1-p)\leq {\frac {1}{4}}.}$

Applying Chebyshev's inequality, we have that for any ${\displaystyle x}$ that ${\displaystyle f(x)=1}$,

{\displaystyle {\begin{aligned}\Pr \left[\bigvee _{i=1}^{t}A(x,r_{i})=0\right]&=\Pr[X=0]\\&\leq \Pr[|X-\mathbf {E} [X]|\geq \mathbf {E} [X]]\\&\leq \Pr \left[|X-\mathbf {E} [X]|\geq {\frac {t}{2}}\right]\\&\leq {\frac {4}{t^{2}}}\sum _{i=1}^{t}\mathbf {Var} [X_{i}]\\&\leq {\frac {1}{t}}.\end{aligned}}}

The error is reduced to ${\displaystyle 1/t}$ with only two random numbers. This scheme works as long as ${\displaystyle t\leq p}$.