StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You should check out the classic paper of Erdos and Renyi from 1960 entitled <a href="http://www.renyi.hu/~p_erdos/1960-10.pdf" rel="noreferrer">"On the evolution of random graphs"</a>. It contains complete probabilistic bounds for number of components, size of the largest components, etc.</p> <p>Here's a bit of the math set-up to get you started.</p> <p>Let <code>G(n,m)</code> be the simple random graph on <code>n</code> vertices with <code>m</code> edges. Let <code>X_k</code> be the number of edges added while there are <code>k</code> connected components until there are <code>k-1</code> connected components. For example, initially there are <code>n</code> connected components, so adding the first edge results in <code>n-1</code> connected components so <code>X_n = 1</code>. Similarly, the second edge also removes a component (though this happens in one of two ways) so <code>X_n-1 = 1</code> as well. Define</p> <pre><code>X = X_n + X_n-1 + ... + X_2 </code></pre> <p>The goal is to compute <code>E(X)</code>, the expected value of <code>X</code>. By additivity, we have</p> <pre><code>E(X) = E(X_n) + E(X_n-1) + ... + E(X_2) </code></pre> <p>It's not too hard to show that the probability that an edge added while there are <code>k</code> components reduces the number of components has a lower bound of <code>(k-1)/(n-1)</code>. Since <code>X_k</code> is the random variable with probability of success given by this amount, the lower bound gives an upper bound for the expectation of <code>X_k</code>:</p> <pre><code>E(X_k) <= (n-1)/(k-1) </code></pre> <p>Combining this, we get an asymptotic upper bound for <code>E(X)</code> by <code>n log n</code>. </p> <p>With a bit more work and some hints from the Erdos-Renyi paper, you can probably deduce an exact formula.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload