Wednesday, June 10, 2009

Probability of a graph being connected...

I ran across the following question in a problem I'm working on, and thought I'd ping the collective wisdom of the blog-reader-o-sphere.
Given an undirected graph G with (possibly different) probabilities on edges, consider the usual random process where we pick each edge independently, but with probability p_e (this is the difference from the standard erdos-renyi model).

What is the probability that the resulting graph is connected ?

This seems possibly to have something to do with the spanning tree polytope, but it seems quite nontrivial. In general, I'm given a subset of vertices S in this graph, and want to ask for the probability that S forms a connected component. Making sure that S is disconnected from the rest of the graph is easy, but then the remainder of the probability comes from the answer to the above question.

I should add that the subset connectivity question is trivial if G is a tree: it's the higher connectivity case that makes things harder.

p.s More SoCG posts should be on their way in the next few days after I return.