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.
