How to prove that $ P(\alpha(G)\ge k)\le \binom{n}{k}q^{\binom{k}{2}} $?

29 Views Asked by At

Let $G\in \mathcal{G}(n,p)$ be a Erdos-Renyi random graph. Let $\alpha(G)$ be the maximal number of the independent set of $G$. Here is a Lemma as follows.

For all integers $n\ge k\ge 2$, the probability $G\in \mathcal{G}(n,p)$ has a set of $k$ independent vertices is at most $$ P(\alpha(G)\ge k)\le \binom{n}{k}q^{\binom{k}{2}} $$

I can get that for a fixed $k-$independent set $U\subset V(G)$, the probability of $U$ in $G$ is $q^{\binom{k}{2}}$. Since the number of such $U$ is $\binom{n}{k}$. Then we have $$ P(\alpha(G)= k)=P(\{U\})=\binom{n}{k}q^{\binom{k}{2}} $$

But how to prove this upper bound?

1

There are 1 best solutions below

0
On BEST ANSWER

Your equation is not quite right. Note that just because there is a set $U$ of $k$ vertices in $G$ that do not have any edges between them, it does not mean that the independence number is exactly $k$. It actually implies that the independence number is at least $k$ ($U$ is an example of a $k$-independent set, but there could be a larger one).

The calculation that for a fixed set $U$ of $k$ vertices in $G$, the probability that there are no edges between them is $q^{\binom{k}{2}}$ is correct (with $q = 1 - p$). So to argue more correctly, you can apply the union bound: $$ \begin{align} \mathbb{P}(\alpha(G) \geq k) &= \mathbb{P}(\exists \text{ $k$-independent set } U \subseteq V) \\ &\leq \sum_{U \subseteq V, |U| = k} \mathbb{P}(U \text{ is a $k$-independent set}) \\ &= \binom{n}{k} q^{\binom{k}{2}} . \end{align} $$