9
$\begingroup$

Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are known - in particular, $G(n,p)$ is almost surely connected when $p \gt (1 + \epsilon)\frac{\log(n)}{n}$, and the largest clique in $G(n, \frac{1}{2})$ is almost surely about $2\log_2(n)$.

What is known about the vertex connectivity number $\kappa(G)$, $G\in G(n,p)$, the minimum number of vertices that one must remove in order to disconnect the graph?

It is known that for fixed $k$ and fixed $p\in (0,1)$, almost every graph in $G(n,p)$ is $k$-connected, but what is the expected connectivity as a function of $p$ and $n$?

$\endgroup$
1
  • $\begingroup$ Yes, you are correct. $\endgroup$ Jun 16, 2010 at 0:42

1 Answer 1

6
$\begingroup$

The expected connectivity cannot be higher than the expected minimal degree, which jumps to roughly $pn$ after getting into the range $p\gg\frac{\log n}{n}$. On the other hand, sloppily counting potential clusters of size $m < n/2$ that have boundaries of less than $k$ vertices gives a probability of $\binom{n}{m}\binom{n-m}{k}(1-p)^{m(n-m-k)}$, which is for $k \ll n$ decreasing in $m$ up to $m\approx \frac{n-k}{2}$ and increasing after that value, so we can get an estimate by considering only $m=1$ (checking for vertices with at most $k$ neighbours) and $m=\frac{n}{2}$: $$ \binom{n}{n/2}\binom{n/2}{k}(1-p)^{n(n-2k)/4} < \exp(n \log 2+k \log n - pn(n-2k)/4) < $$ $$ < \exp(n \log 2 - pn(\frac{n}{4}-\frac{k}{2}-\log n)) < \exp(-\frac{n \log n}{4} + n \log 2 +2(\log n)^2), $$ this latter number tending to $0$ fast enough to ignore it. So, the expected connectivity is the expected minimal degree and is roughly $pn$ once $p$ exceeds $\log n/n$. Do you need the behaviour of expected connectivity specifically in this region?

$\endgroup$
1
  • $\begingroup$ Thanks Thorny - this was very helpful. So the $E(\kappa(H))$ tends to around $\frac{n}{2}$ for $H \in G(n,p)$, which is what I was most interested in. $\endgroup$ Jun 16, 2010 at 15:08

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.