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

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.

Edit (14 March 2014)

After Brendan McKay's helpful comment, I found the formula $$R_n(p) = \sum_{j=1}^{n-1}{\binom{n-1}{j-1}(1-p)^{j(n-j)}R_j(p)},\quad R_1(p)=1,$$ for the all-terminal reliability polynomial $R_n$ of the complete graph on $n$ vertices (i.e. the probability that the graph remains connected after deleting edges with probability $p$) and the formula $$T_n(p) = \sum_{j=2}^{n}{\binom{n-2}{j-2}(1-p)^{j(n-j)}R_j(p)}$$ for the 2-terminal reliability polynomial (i.e. the probability that vertices 1 and 2 are in the same connected component after deleting edges with probability $p$).

The experimentalist that I am, I used the first recursion to compute $R_n$ for a few values of $n$ and tried to guess a pattern for its coefficients.

What I found is that $\frac{R_n(1-p)}{(1-p)^{n-1}}$ is a polynomial of degree $(n-2)(n-1)/2$ and that the coefficients of its monomials with small exponent seem to be given by $$[p^i]\frac{R_n(1-p)}{(1-p)^{n-1}} = \color{blue}{\binom{n-2+i}{n-2},\quad i=0,1,\ldots,n-2}.\tag{*}$$

For the monomials with large exponents there appear to exist polynomials $\mathfrak{p}_j$ of degree $j$ such that, for $\color{green}{i=\frac{(n-2)(n-1)}{2}-n+1,\ldots,\frac{(n-2)(n-1)}{2}}$, $$[p^i]\frac{R_n(1-p)}{(1-p)^{n-1}}=\color{green}{\frac{(n-1)!}{\left[2\left(\frac{(n-2)(n-1)}{2}-i\right)\right]!!}\mathfrak{p}_{\frac{(n-2)(n-1)}{2}-i}(n)},\tag{**}$$ where !! denotes the double factorial. The first few polynomials $\mathfrak{p}_j$ appear to be given by $$\begin{array}{c|c} j&\mathfrak{p}_j\\\hline 0 & 1 \\ 1 & n-2\\ 2 & n^2-3 n\\ 3 & n^3-3 n^2-2 n\\ 4 & n^4-2 n^3-5 n^2-18 n\\ 5 & n^5-5 n^3-80 n^2+4 n\\ 6 & n^6+3 n^5+5 n^4-195 n^3-86 n^2-848 n\\ 7 & n^7+7 n^6+35 n^5-315 n^4-476 n^3-6132 n^2+160 n \end{array}$$ The leading coefficients seems to be one; the next-to-leading coefficient in $\mathfrak{p}_j$, i.e. $[p^{j-1}]\mathfrak{p}_j$, appears (tentatively) to be given by $j(j-5)/2$. I haven't had a chance to look at the other coefficients yet.

Unfortunately, the two formulas (*) and (**) cover only a small proportion of the quadratically many coefficients of $\frac{R_n(1-p)}{(1-p)^{n-1}}$, as indicated in the next coefficient table. $$\scriptsize{ \begin{array}{c|cccccccccccccccccccccc} n,i & 0 & 1 & 2 & \ldots\\\hline 2 & \color{blue} 1\\ 3 & \color{blue} 1 & \color{blue}2\\ 4 & \color{blue} 1 & \color{blue}3 & \color{blue}6 & \color{green}6\\ 5 & \color{blue}1 & \color{blue}4 & \color{blue}{10} & \color{blue}{20} & \color{green}{30} & \color{green}{36} & \color{green}{24}\\ 6 & \color{blue}{1} & \color{blue}{5} & \color{blue}{15} & \color{blue}{35} & \color{blue}{70} & \color{green}{120} & \color{green}{180} & \color{green}{240} & \color{green}{270} & \color{green}{240} & \color{green}{120}\\ 7 & \color{blue}{1} & \color{blue}{6} & \color{blue}{21} & \color{blue}{56} & \color{blue}{126} & \color{blue}{252} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{green}{1610} & \color{green}{2100} & \color{green}{2520} & \color{green}{2730} & \color{green}{2520} & \color{green}{1800} & \color{green}{720}\\ 8 & \color{blue}{1} & \color{blue}{7} & \color{blue}{28} & \color{blue}{84} & \color{blue}{210} & \color{blue}{462} & \color{blue}{924} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{red}{?} & \color{green}{24640} & \color{green}{29400} & \color{green}{32970} & \color{green}{34230} & \color{green}{31920} & \color{green}{25200} & \color{green}{15120} & \color{green}{5040} \end{array} }$$

Up to $n=6$, the reliability polynomial of $K_n$ is correctly computed by (*) and (**) but beyond that a growing chunk of coefficients is missing in the middle.

Questions: What are the polynomials $\mathfrak{p}_j$? How can one compute the $\color{red}?$ coefficients?

• 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