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

  • $\begingroup$ Yes, you are correct. $\endgroup$ – Justin Melvin Jun 16 '10 at 0:42

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?

  • $\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$ – Justin Melvin Jun 16 '10 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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