= Connectivity of random k-out graphs
{title2=$\Pr(G_{k\text{-out}}\text{ connected})\to1\quad(k\ge2)$}
For $k=2$, a disconnected <graph> has a component of size $3\le s\le n/2$. The <probability> that a fixed $s$-set has no crossing <edge> is at most $(s/n)^{2s}(1-s/n)^{2(n-s)}$. The <union bound> and $\binom ns\le(n/s)^s[n/(n-s)]^{n-s}$ bound the failure <probability> by $\sum_{s=3}^{\lfloor n/2\rfloor}(s/n)^s=o(1)$. Split this sum at $\sqrt n$. The <random k-out graph> coupling extends the result to every fixed $k\ge2$.
Back to article page
