Probability of intersection of dependent events, having probability approaching 1 in random graph For $\mathcal{G}(n,p)$ (Erdős–Rényi graph) let $A$ be a property of pair of vertices. And let $A_{uv}$ be the event that property $A$ holds for vertices $u$ and $v$. If the following holds
$$\forall u,v \quad \lim_{n \to \infty} \Pr[A_{uv}] = 1$$
then would it be correct to say that
$$\lim_{n \to \infty} \Pr[\bigcap\limits_{u,v}A_{uv}]=1$$
The events $A_{uv}$ are not independent. Intuitively it seems correct, but how I can formally prove/disprove the above.
 A: No it's not correct : If $\Pr[A_{uv}]$ tends to 1 too slowly (e.g. in $1/n$) then this is an issue as the number of pairs grows too fast (in $n^2$) :
For instance assume that for any $u,v$, $\Pr[A_{uv}]=1-\frac{1}{n}$ and assume that the events are independent for simplicity. Then
$$ \Pr[\bigcap_{u,v}A_{uv}] = \left(1-\frac{1}{n}\right)^{\binom{n}{2}} \leq e^{-\binom{n}{2}\frac{1}{n}} = e^{-\frac{n-1}{2}} \to 0$$
This might be understood intuitively by saying that if you want $G\in\mathcal{G}(n,p)$ to be with high probability a complete graph $K_n$, then you need $p$ to tend to 1 very quickly, otherwise you have too many edges, and one of them will not be present in $G$.
A: No, this isn't guaranteed.
Consider $\mathcal G(n, \frac1n)$, and let $A_{uv}$ be the event "there is no edge between $u$ and $v$". Then $\Pr[A_{uv}] = 1 - \frac1n \to 1$ as $n \to \infty$, but $\bigcap_{u,v} A_{uv}$ is the event that the graph has no edges, and the probability of that goes to $0$.
The most typical way to solve the problem is to let $\mathbf X_{uv} = 1$ if $A_{uv}$ does not hold, and $X_{uv}=0$ if $A_{uv}$ does hold. Then $\mathbb E[\mathbf X_{uv}] \to 0$ as $n \to \infty$. Let $\mathbf X = \sum_{u,v} \mathbf X_{u,v}$. If we can show the stronger statement that $\mathbb E[\mathbf X] = \sum_{u,v} \mathbb E[\mathbf X_{u,v}] \to 0$ as $n \to \infty$, then we can conclude that $\mathbf X = 0$ with probability tending to $1$, and so $\bigcap_{u,v} A_{uv}$ holds with probability tending to $1$.
