Let $E^c_n$ be the expected number of connected components of a simple undirected graph on the vertex set $\{1,\ldots,n\}$. (Every possible edge in $\big\{\{a, b\}: a, b\in \{1,\ldots,n\} \land a \neq b\big\}$ is picked with probability $1/2$.)

Is $\{E^c_n: n\in\mathbb{N}\}$ bounded? If yes, what is the least upper bound, and if no, do we have $\lim \sup_{n\to\infty}\frac{E^c_n}{n} = 0$?


$E_{n+1}^c \leq E_n^c + \frac{1}{2^n}$, so as $E_0^c = 0$, we have that $E_n^c \leq 2$.

Reason: For a graph $G$, define $|G^c|$ as the number of components of $G$. Then for any labeled graph $G$, there are $2^n$ graphs with $n + 1$ vertices such that the subgraph on the first $n$ vertices is $G$. The one such that none of those "new" edges exists has exactly 1 more component, while the rest have at most as many components as $G$.

The case where the edge probability decreases proportional to $\frac{1}{n}$ seems to be more studied; according to Wikipedia (https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model), "Almost every graph in G(n, 2ln(n)/n) is connected", so in fact the limit should be 1.

  • $\begingroup$ For $G \sim G_{n,1/2}$ we can say that $G$ has diameter $2$ with absurdly high probability, so the expectation is certainly $1+o(1)$. $\endgroup$ – Ben Barber Mar 10 '17 at 8:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.