# Edge probability for connected Erdős–Rényi model

Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there exists an edge between $x$ and $y$.

I need to estimate (especially bound from above) the following probability for two fixed vertices $x,y$ and $G \in G_{n,p}$:

$$$\mathbb{P}_{n,p}[E_{x,y}|G \text{ is connected}]$$$

Supplement: $p=\frac{c}{n}$ for some constant $c >1$ (I forgot this in my first version).

• Do you need a complete description for any given function $p\colon \omega\to(0,1)$ ? If $p$ is any function $p\colon \omega\to(0,1)$ such that $p\gg\frac{\log n}{n}$, then $\lim_{n\to\infty}\frac{\mathbb{P}_{n,p(n)}[E_{x,y}\mid\text{$G$is connected}]}{p(n)} = 1$. If, however, you 'are' 'inside' 'the' 'phase-transition' for the connectedness, then giving a thorough answer would require a bit of work, I think. – Peter Heinig Oct 7 '17 at 15:10
• Without meaning to prescribe you anything, for known reasons the question would be most interesting if you stipulated that $p(n) = n^{-1} + n^{-\frac43}$. You probably shouldn't do this for the sake of asking a harder question; it might be that in your work you only need a 'regime' of functions $p\colon\omega\to(0,1)$ for which the question is trivial, by superficial calculations. My point is mainly that you should make you question more precise, by specifying which functions $p\colon \omega\to(0,1)$ you need; the effects of that range from 'trivial' to 'difficult' (I think). – Peter Heinig Oct 7 '17 at 15:37
• @PeterHeinig: The question is about any fixed $n$ and $p$. The OP doesn't seem to be (immediately) interested in limiting probabilities or asymptotic estimates. It seems to me that you are making the question much more difficult than it is. – François G. Dorais Oct 7 '17 at 20:59
• 'François G. Dorais' is right in saying that if one interprets this OP strictly logically, then it is asking about the stated probability with '$n$' and '$p$' being constants (in the model-theoretic sense of 'constant'). My comments are imputing intentions to the opening poster, but I thought I had made it abundantly clear that I was imputing intentions, and that I was pointing out to the opening poster that they should not adopt my suggested additional hypotheses merely for the sake of making it a hard question, rather should make the clarifications fit whatever actual intents they have. – Peter Heinig Oct 8 '17 at 6:02
• @FrançoisG.Dorais: I think you have it the wrong way around. Giving a useful answer to such a question "for any fixed $n$ and $p$" can typically be very hard. On the other hand, there are "regimes" of $n$ and $p$ (i.e. ways in which $p$ behaves as a function of $n$, as $n$ grows), where the answer can be more straightforward. It would certainly be useful if the OP could clarify whether they are interested in a particular regime. – James Martin Oct 8 '17 at 9:39

Let $E_{xy}$ be the event that $xy$ is an edge of $G$ and let $C$ be the event that $G$ is connected. By Bayes' Theorem, $$P(E_{xy} \mid C) = \frac{P(C \mid E_{xy})P(E_{xy})}{P(C)} = p\frac{P(C \mid E_{xy})}{P(C)}.$$ So the question amounts to estimating how much knowing that $G$ has an edge improves the probability of $G$ being connected.

The graph $G$ is connected precisely if it contains a spanning tree $T$. Furthermore, knowing that $xy$ is an edge of $G$, we may further require that $T$ contains the edge $xy$. So we have a crude upper bound $$P(C \mid E_{xy}) \leq \sum_{xy \in T} P(T \subseteq G \mid E_{xy}),$$ where $T$ ranges over all trees on the labeled vertex set $\{1,\ldots,n\}$. By Cayley's Formula, there are $n^{n-2}$ such $T$ and, since each such $T$ has exactly $n-1$ edges, there are $2n^{n-3}$ such trees that contain the edge $xy$. For each $T$ containing $xy$, $P(T \subseteq G \mid E_{xy}) = p^{n-2}$, so $$P(C \mid E_{xy}) \leq 2n^{n-3}p^{n-2},$$ or equivalently $$P(E_{xy} \mid C) \leq \frac{2n^{n-3}p^{n-1}}{P(C)}.$$ Clearly, this bound is only useful for small $p$. When $p$ is large, the trivial bound $$P(E_{xy} \mid C) \leq \frac{p}{P(C)}$$ is of greater use.

The classic paper Gilbert, E.N., Random graphs, Ann. Math. Stat. 30, 1141-1144 (1959). ZBL0168.40801, contains exact formulas for $P(C)$. Gilbert's method can also be used to compute $Q_n = P(C \mid E_{xy})$ using the recurrence $$1-Q_n = \sum_{k=2}^{n-1} \binom{n-2}{k-2}Q_k(1-p)^{k(n-k)}.$$ (The $k$th term is the conditional probability that the connected component containing $x,y$ has exactly $k$ elements.) Thus

$Q_{2} = 1$

$Q_{3} = -p^2 + 2 p$

$Q_{4} = -2 p^5 + 9 p^4 - 14 p^3 + 8 p^2$

$Q_{5} = 6 p^9 - 48 p^8 + 162 p^7 - 298 p^6 + 318 p^5 - 189 p^4 + 50 p^3$

I haven't tried to prove it but it seems that the bound $2n^{n-3}p^{n-2}$ from above is exactly the leading term of $Q_n$. At least this is the case for $n \leq 60$ by direct calculation.

• I don't understand this. The formula in display is much too small when, say, $p=1/2n$. – Ori Gurel-Gurevich Oct 8 '17 at 7:47
• @OriGurel-Gurevich: Yes, I forgot to condition on connectedness. Thanks! I fixed it, but then I found a slightly better bound which is hopefully clearer. – François G. Dorais Oct 8 '17 at 10:27
• I've asked the implicit question in the last paragraph here: mathoverflow.net/q/282996 – François G. Dorais Oct 8 '17 at 16:20

I agree strongly with Peter in the comments: if you're interested in $p \gg \frac{\log n}{n}$, then don't do any hard work, just show the answer is essentially $p$ since the graph is essentially always connected.

In particular, let $E$ be the event that the edge exists and $C$ the event that the graph is connected. By the law of total probability, \begin{align*} P(E|C)P(C) + P(E,\lnot C) &= p \end{align*} so \begin{align*} P(E|C) &= \frac{p - P(E,\lnot C)}{P(C)} \\ &\leq \frac{p}{1-o(1)} \end{align*} where a lot is known about bounds on the $o(1)$ (the probability the graph is disconnected).

(By the way, naturally, we immediately have $P(E|C) \geq p$. To prove it, $P(E|C) = p P(C|E)/P(C)$, and $P(C|E) \geq P(C)$ as guaranteed existence of $(x,y)$ can only raise the chance of connectedness.)