Return to Revisions

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?