0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

4
$\begingroup$

$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.

$\endgroup$
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, 2017 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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