# 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\ge 1]\rightarrow 0 }$ as $\displaystyle{ n\rightarrow\infty }$. If $\displaystyle{ p=\omega(n^{-2/3}) }$, then $\displaystyle{ \Pr[X\ge 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\ge 1]\le \mathbf{E}[X]=O(n^4p^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]\le\Pr[|X-\mathbf{E}[X]|\ge\mathbf{E}[X]]\le\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\le \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^4p^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|\le 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_SX_T]-\mathbf{E}[X_S]\mathbf{E}[X_T]\le\mathbf{E}[X_SX_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^6p^{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)\le\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^5p^{9}) }$. Putting all these together, $\displaystyle{ \mathbf{Var}[X]=O(n^4p^6+n^6p^{11}+n^5p^{9}). }$ And $\displaystyle{ \Pr[X=0]\le\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)\le \rho(G) }$ for all subgraphs $\displaystyle{ H }$ of $\displaystyle{ G }$.

Cliques are balanced, because $\displaystyle{ \frac{{k\choose 2}}{k}\le \frac{{n\choose 2}}{n} }$ for any $\displaystyle{ k\le 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}\le\mathbf{E}[X_S]\le 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^kp^{\ell}) }$. By Markov's inequality, $\displaystyle{ \Pr[X\ge 1]\le \mathbf{E}[X]=\Theta(n^kp^{\ell}) }$ which is $\displaystyle{ o(1) }$ when $\displaystyle{ p\ll n^{-\ell/k} }$. By Chebyshev's inequality, $\displaystyle{ \Pr[X=0]\le \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]\le \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^kp^{\ell}) }$. For the covariances, $\displaystyle{ \mathbf{Cov}(X_S,X_T)\neq 0 }$ only if $\displaystyle{ |S\cap T|=i }$ for $\displaystyle{ 2\le i\le 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})\ge 2\ell-i\rho(H)=2\ell-i\ell/k }$. Thus, $\displaystyle{ \mathbf{Cov}(X_S,X_T)\le\mathbf{E}[X_SX_T]\le 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]\le \frac{\mathbf{Var}[X]}{\mathbf{E}[X]^2}\le \frac{\Theta(n^kp^{\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{align} Y_i=(X_0+i\cdot X_1)\bmod p &\quad \mbox{for }i\in[p]. \end{align} }
 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{align} \Pr\left[(X_0+i\cdot X_1)\bmod p=a\right] &= \frac{1}{p}. \end{align} } Due to the law of total probability, \displaystyle{ \begin{align} \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{align} } 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{align} \Pr\left[Y_i=a\wedge Y_j=b\right] &= \frac{1}{p^2}. \end{align} } 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]\ge\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{align} \forall 1\le i\le t, &\quad \mbox{let }r_i = (a\cdot i+b)\bmod p. \end{align} } 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\le 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}^tX_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]\ge\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]\ge\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)\le\frac{1}{4}. }$

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

\displaystyle{ \begin{align} \Pr\left[\bigvee_{i=1}^t A(x,r_i)=0\right] &= \Pr[X=0]\\ &\le \Pr[|X-\mathbf{E}[X]|\ge \mathbf{E}[X]]\\ &\le \Pr\left[|X-\mathbf{E}[X]|\ge \frac{t}{2}\right]\\ &\le \frac{4}{t^2}\sum_{i=1}^t\mathbf{Var}[X_i]\\ &\le \frac{1}{t}. \end{align} }

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