MHB What Factors Influence the Number of Connected Components in Random Graphs?

[repoman1]

Having a hard time with this problem. Can anyone guide me in the correct direction?

Random graphs are a fascinating subject of applied and theoretical research. These can be generated with a fixed vertex set V and edges added to the edge set E based on some probability model, such as a coin flip. Speculate on how many connected components a random graph might have if the likelihood of an edge (v1,v2) being in the set E is 50%. Do you think the number of components would depend on the size of the vertex set V? Explain why or why not.

 

[Evgeny.Makarov]

I assume the likelihood of an edge $(v_1,v_2)$ is the same for all pairs of vertices $(v_1,v_2)$, and the presence of an edge is independent of other edges. Suppose a random graph with these properties has two connected components with $m$ and $n$ vertices, respectively. There are $mn$ edges that are missing between these two components, and the probability of that is $2^{-mn}$, which is exceedingly small for large $m$, $n$.

For more details, consult Wikipedia about Erdős–Rényi model of random graph generation. It turns out that if $p<\frac{(1-\varepsilon)\ln n}{n}$ for some $\varepsilon>0$, then a random graph with $n$ vertices where the probability of an edge is $p$ will almost surely be disconnected, and if $p>\frac{(1+\varepsilon)\ln n}{n}$, then a random graph with $n$ vertices will almost surely be connected. Since $\frac{\ln n}{n}\to0$ as $n\to\infty$, the threshold probability for connectedness is very small for large graphs, certainly smaller than 0.5.