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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Mar 10, 2017 at 8:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .