6
$\begingroup$

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.

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?

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 12, 2013 at 0:36
  • $\begingroup$ 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$? $\endgroup$ Aug 26, 2013 at 22:27

1 Answer 1

1
$\begingroup$

Explicit expressions for the all-terminal reliabilty were established back in 1959 by Gilbert.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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