Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed (distinct) vertices $u,v$ lie in the same connected component of $G(n,p)$?

I'm familiar with the standard asymptotic results about connected components in Erdős–Rényi graphs but was unable to find explicit results for $P_{n,p}$ for finite $n$. I expect these probabilities to be polynomials in $p$ of degree $n(n-1)/2$ but did not succeed in determining the coefficients for general $n$ and $p$.


Explicit expressions for the all-terminal reliabilty $R$ were established back in 1959 by Gilbert. The two-terminal reliability function (which is what the question was about) can then be computed in terms of $R$.

See also the corresponding post on mathoverflow.

Gilbert, E. N. Random graphs. Ann. Math. Statist. 30 1959 1141--1144. MR0108839 (21 #7551)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.