Probability of intersection of dependent events, having probability approaching 1 in random graph

99 Views Asked by At

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.

2

There are 2 best solutions below

0
On BEST ANSWER

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

0
On

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