most recent 30 from http://mathoverflow.net 2013-05-22T22:21:00Z http://mathoverflow.net/feeds/question/28299 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28299/vertex-connectivity-of-random-graphs Justin Melvin 2010-06-15T18:26:42Z 2010-06-16T09:36:38Z

<p>Consider simple, undirected 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). </p> <p><b>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? </b></p> <p>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$?</p>

http://mathoverflow.net/questions/28299/vertex-connectivity-of-random-graphs/28366#28366 Thorny 2010-06-16T09:16:29Z 2010-06-16T09:16:29Z

<p>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 &lt; 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 &lt; &lt; 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} &lt; exp(n \log 2+k \log n - pn(n-2k)/4) &lt; $$ $$ &lt; exp(n \log 2 - pn(\frac{n}{4}-\frac{k}{2}-\log n)) &lt; 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?</p>