Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
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

1 Answer 1

up vote 1 down vote accepted

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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