Two random graph models
Binomial model \(G(n,p)\)
\(\Omega\) is the set of all graphs on \([n]\), the probability measure on \(\Omega\) is given by
\[\mathbb{P}_B\{G\} = p^{e_G}(1-p)^{N-e_G}, \quad e_G = |E(G)|, \quad N = \binom{n}{2}\]
where \(e_G\) is the number of edges in \(G\) and \(N\) is the total number of edges in the complete graph on \([n]\).
The Uniform model \(U(n,m)\) where \(m\le \binom{n}{2}\).
\(\Omega\) is the set of all graphs with \(m\) edges on \([n]\), the probability measure on \(\Omega\) is uniform on all graphs with \(m\) edges.
\[\mathbb{P}_U\{G\} = \frac{1}{\binom{N}{m}}, \quad N = \binom{n}{2}\]
Random subsets
For the binomial model, let \(\Gamma = \wedge^2[n]\) be the family of two elements subsets of \([n]\). We know that \(|\Gamma| = N = \binom{n}{2}\).
Define \(\Gamma_p\) to be a random variable, with value in the set \(\Gamma\), whose distribution is given by choosing each edge with independent probability \(p\). I.e. its distribution is given by the following probability measure on \(\Gamma\):
\[\mathbb{P}(\Gamma_p = g) = p^{e_g}(1-p)^{N-e_g}, \quad e_g = |E(g)|, \quad N = \binom{n}{2}\]
where \(g\in \Gamma\) is a graph on \([n]\).
For the uniform model, let \(\Gamma_m\) be a random variable with value in the set \(\Gamma = \wedge^m(\wedge^2 [n])\) whose distribution is given by choosing \(m\) edges uniformly at random from the set of all edges in the complete graph on \([n]\). I.e. its distribution is given by the following probability measure on \(\Gamma\):
\[\mathbb{P}(\Gamma_m = g) = \frac{1}{\binom{N}{m}}, \quad N = \binom{n}{2}\]
Graph property
A graph property is a property of a graph that is invariant under isomorphism. I.e. a family of graphs \(Q\subset \Omega\) closed under isomorphism, if \(G\cong H\) then \(G\in Q\) if and only if \(H\in Q\).
Proposition Let \(Q\) be an graph property of graphs on \([n]\). Let \(p=p(n)\) and \(0\le a \le 1\) be some constant. If for every sequence of \(m=m(n)=Np + O\left(\sqrt{Np(1-p)}\right)\), the property under uniform model has a limit, then it also has the same limit under the binomial model. I.e.
\[\mathbb{P}(\Gamma_m \in Q)\xrightarrow{n\to \infty} a \Rightarrow \mathbb{P}(\Gamma_p \in Q)\xrightarrow{n\to \infty} a . \]
This is some phenomenon we encounter like in percolation theory, a sudden change of phases when we increase the parameter \(p\). But here the threshold is defined up to asymptotic equivalence with constant factors.
Let \(Q\) be a property of random subsets of a sequence \(\Gamma(n)\) of sets, write \(N(n)=|\Gamma(n)|\).
For an increasing property, a sequence \(\hat{p}(n)\) is called a threshold if
\[\mathbb{P}(\Gamma_p\in Q)\to \begin{cases} 0 & \text{if } p / \hat{p}(n)\to 0\\ 1 & \text{if } p / \hat{p}(n)\to \infty \end{cases} \]
Similarly, a sequence \(\hat{m}(n)\) is called a threshold if
\[\mathbb{P}(\Gamma_m\in Q)\to \begin{cases} 0 & \text{if } m / \hat{m}(n)\to 0\\ 1 & \text{if } m / \hat{m}(n)\to \infty \end{cases} \]
For decreasing properties, thresholds are defined as the thresholds for the complementary property (which is increasing).
If for \(n\) large enough, we have \(c\hat{p} \le \hat{p}' \le C \hat{p}\), then it means that \(\hat{p}'\) is also a threshold. Clearly thresholds are defined only up to asymptotic equivalence with constant factors. The same holds for \(m\).
The function \(\hat{p}=\frac{1}{n}\) is a threshold for the graph having a cycle.
For a given increasing property \(Q\), and \(a\in (0,1)\), define
\[p(a,n) = \inf\{p : \mathbb{P}(\Gamma_p\in Q) = a\}\]
they exist and is well defined because \(p\mapsto \mathbb{P}(\Gamma_p\in Q)\) is continuous and non-decreasing.
Similarly we can define
\[m(a,n) = \inf\{m : \mathbb{P}(\Gamma_m\in Q) \ge a\}\]
But here we have to use \(\ge\) because the corresponding function in \(m\) is not continuous.
Proposition. Let \(Q\) be an increasing property of subsets of \(\Gamma = \Gamma(n)\). Then \(\hat{p}(n)\) is a threshold iff
\[\frac{p(a,n)}{\hat{p}(n)} \asymp 1.\]
This basically says that \(p(a,n)\) is one of the threshold you can choose.
Recall that if \(Q\) is an increasing property of subsets of \(\Gamma\), \(0\le p_1\le p_2\le 1\) and \(0\le m_1\le m_2\le N\), then
\[\mathbb{P}(\Gamma_{p_1}\in Q) \le \mathbb{P}(\Gamma_{p_2}\in Q)\]
Theorem (Bollobas-Thomason). Every monotone property has a threshold.
We are interested in the width of the thresholds! Define for \(\varepsilon \in \left(0,\frac{1}{2}\right)\),
\[\delta(\varepsilon, n) = p(1-\varepsilon, n) - p(\varepsilon, n)\]
Certain monotone properties sharper thresholds.
Theorem (Erdos-Reny 1960). Let \(p(n) = \frac{\log n + c_n}{n}\) where \(-\frac{\log{n}}{2} \le c_n \le c\log n\) with \(c>0\), then
\[\lim_{n\to \infty} \mathbb{P}(G(n,p)\text{ is connected}) = \begin{cases} 0 & \text{if } c_n\to -\infty\\ e^{-e^{-c}} & \text{if } c_n\to c \\ 1 & \text{if } c_n\to +\infty \end{cases} \]
Idea of proof:
Consider the following sets
\(C\): \(G(n,p)\) is connected
\(B_1\): \(G(n,p)\) has a isolated vertex
\(B_2\): \(G(n,p)\) has no isolated vertex and is not connected
Clearly \(C = B_1^c \cap B_2^c = (B_1 \cup B_2)^c\) and \(B_1\cap B_2 = \varnothing\). Thus
\[\mathbb{P}(C) = 1 - \mathbb{P}(B_1) - \mathbb{P}(B_2).\]