Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider simple, undirected http://en.wikipedia.org/wiki/Erdős–Rényi_model>Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability any pair of vertices 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 2log$_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$?

share|improve this question
Yes, you are correct. –  Justin Melvin Jun 16 '10 at 0:42
add comment

1 Answer

up vote 3 down vote accepted

The expected connectivity cannot be higher than the expected minimal degree, which jumps to roughly $pn$ after getting into the range $p>>\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 < < 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?

share|improve this answer
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. –  Justin Melvin Jun 16 '10 at 15:08
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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