# Probability of two vertices to be connected in G(n,p)

A question I asked at math.SE without elliciting an answer.

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

I fed the values of $P_{n,1/2}$, for $n=2,3,4,5$, into OEIS, but did not obtain a match.

-
This is called the two-terminal reliability polynomial (or reliability function) of a complete graph. I don't know if there are explicit expressions, but searching with those keywords might uncover something. arxiv.org/pdf/cs/0612143.pdf mentions it. –  Brendan McKay Mar 12 '13 at 0:36
Shouldn't be possible to bound it from above with something along the lines of: $\rho(c)^2 + \left(\frac{K(c)\log n}{n}\right)^2 \cdot (1-\rho(c))n$, where $\rho(c)$ is the proportion of nodes in the giant component when $p = \frac{c}{n}$ and $K(c)$ is a function that does not depend on $n$? –  tipanverella Aug 26 '13 at 22:27
add comment