1
$\begingroup$

In this proof from "The Probabilistic Method" by Alon and Spencer, p.206, they argue that if $v$ is an aribtrary vertex with connected component of size $k$, then there is probability $O(p^k)=O(n^{-k})$ that $G(n,p)$ has more than $k-1$ edges in this connected component. Here $p=c/n$.

I'm having trouble seeing why this is the case. The connected component has $\binom{k}{2} - (k-1)$ other possible edges to consider. We want the probability that at least one of them is on. Isn't this $1-(1-p)^{\binom{k}{2} - (k-1)}$? If so, how is this expression $O(p^k)$? Furthermore, what is changing in the big-oh notiation here? Is $k \to \infty$?

Edit:

This comes up in the proof the following fact: $$P[T_c^{Po}=k] = \lim_{n \to \infty} P[|C(v)|=k].$$

Here $T_c^{Po}$ is the progeny size of the branching process with Poisson distribution with mean $c$.

$\endgroup$
  • $\begingroup$ We need more context. $O(p^k)$ is the probability that (for constant $k$) a set of $k$ vertices has more than $k-1$ edges. But $C(v)$ is not an arbitrary set of $k$ vertices; we've already examined many of these potential edges to determine $C(v)$. $\endgroup$ – Misha Lavrov Mar 5 at 19:27
  • $\begingroup$ (Also, my copy of the book is in the middle of discussing circuit complexity on p.206, so maybe you would do better to describe the specific subsection and result being proved rather than just give a page number.) $\endgroup$ – Misha Lavrov Mar 5 at 19:28
  • $\begingroup$ I tried to add a bit more context. But could please explain why $O(p^k)$ is the probbility that a set of $k$ vertices has more than $k-1$ edges? I see that it will have precisely $k$ edges with probability $p^k$, but it could also have $k+1$ edges, or $k+2$ edges, ... How does all this get "eaten up" by the big-Oh? $\endgroup$ – theQman Mar 5 at 19:58
1
$\begingroup$

Let $S$ be a set of $k$ vertices. There are $\binom{\binom k2}{k}$ ways to choose a set $E$ of $k$ edges. For any particular such set $E$, the probability is $p^k$ that all $k$ edges are present.

If we want to know whether $S$ spans at least $k$ edges, this is the union of all $\binom{\binom k2}{k}$ of these events. The events are not independent and in fact there is lots over overlap. However, we can write $$ \Pr[S \text{ spans at least $k$ edges}] \le \binom{\binom k2}{k} p^k $$ by the union bound: the probability would be maximized if the events were disjoint.

This probability is $O(p^k)$ if we are considering $n \to \infty$, $p = \frac cn$, and $k$ constant. In this case, $\binom{\binom k2}{k}$ is just another (really big) constant, so it can be ignored.

$\endgroup$
  • $\begingroup$ Thank you. There is something else I don't understand in the setup of this proof. They claim that "There are $\binom{n}{k-1}$ choices for $S \equiv C(v)...$", here $v$ is in arbitrary vertex and $C(v)$ its connected component. Why is this $\binom{n}{k-1}$? Shouldn't it be $\binom{n-1}{k-1}$? I don't think it's a typo beause they use $\binom{n}{k-1}$ again later on in the proof (although I'm not sure an $n-1$ would change much). $\endgroup$ – theQman Mar 7 at 18:16
  • $\begingroup$ I also think it should be $\binom{n-1}{k-1}$, but you're right that it doesn't make a difference asymptotically. $\endgroup$ – Misha Lavrov Mar 7 at 18:25

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.