Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying a problem that I can model as a random graph. In the basic model, I have a set of vertices that I connect by adding edges. At each stage, I randomly select two vertices and add an edge between them, so an edge could be added more than once. In this case I can either give it a higher weight or just ignore the fact that it was chosen twice - it doesn't matter for my application.

I am interested in the number of connected components as a function of the number of edges I added. What does this distribution look like?

I would like to answer questions like "how many edges do I need to pick to have at least one connected component of size $S$ with probability smaller than $\epsilon$ ?"

I should mention that I am using this for application to a real-life problem, so I am less interested in asymptotic behavior. Specifically, generating edges is associated with a "cost" so I would like to know how many edges I need to generate in order to achieve a given connectivity.

Does anyone have some pointers to relevant material? I found a lot of material on random graph connectivity but would appreciate some material directly relevant to my question, as it is seems pretty straightforward.

share|improve this question
1  
Section 16.1 of Bollobás's Random Graphs contains a table of probabilities that an Erdos-Rényi random graph $G_{n,p}$ is connected for $p = (c + \log n)/n$, $c$ a constant between $-0.83$ and $4.61$, and $n \leq 40000$. –  Andrew Uzzell Dec 17 '12 at 14:57

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.