Probability a random graph has a subset of $t$ vertices with $3t$ edges

128 Views Asked by At

Let $G \sim \mathcal{G}(n,\tfrac{1}{n})$, and let $A$ stand for the event that there exist a set of $1\leqslant t \leqslant \tfrac{n}{10}$ vertices in $G$ on which there are $3t$ edges.

I want to prove that $\text{Pr}(A)\xrightarrow{n\to\infty} 0$

As there are $\binom{n}{t}$ combinations of choosing $t$ vertices out of $n$ vertices, $ n \cdot t$ possible edges from $t$ vertices to $n$ vertices and the probability of having $3t$ edges is $\tfrac{1}{n^{3t}}$ (as we don't care about the rest) I came up with the expression

$$\text{Pr}(A)=\sum_{t=1}^\tfrac{n}{10} \binom{n}{t}\cdot n\cdot t \cdot \frac{1}{n^{3t}}$$

This expression is clearly bounded by:

$$\binom{n}{\tfrac{n}{10}}\cdot n^2 \cdot\sum_{t=1}^\tfrac{n}{10} \left(\frac{1}{n^{3}}\right)^t$$

but this expression doesn't look like it tends to $0$.

Where is my mistake?

1

There are 1 best solutions below

7
On BEST ANSWER

Rather than $n \cdot t$, you have $\binom{\binom t2}{3t}$ ways to pick which $3t$ of the $\binom t2$ edges are present in the graph.

Aside from that, your mistake is pulling out the $\binom {n}{n/10}$ factor from all terms of the sum; your goal should be to put an upper bound on each term of the sum separately.

We have $$ \binom nt \binom{\binom t2}{3t} \frac1{n^{3t}} \le \left(\frac{ne}{t}\right)^t \left(\frac{\binom t2 e}{3t}\right)^{3t} \frac1{n^{3t}} $$ by using the well-known bound $\binom nk \le (\frac{ne}{k})^k$. From here, just combine these factors into a single factor raised to the $t^{\text{th}}$ power: $$ \left(\frac{ne}{t} \cdot \frac{(t-1)^3 e^3}{6^3} \cdot \frac1{n^3}\right)^t. $$

For $t \le \frac{n}{10}$, we can conclude that the value inside the factor is at most $\frac{1}{100}$ or so, so we get an upper bound on our sum: $$ \Pr(A) \le \sum_{t=1}^{n/10} \left(\frac1{100}\right)^t. $$ However, this isn't good enough: in particular, for $t=1$ we get a term equal to $\frac1{100}$.

Instead, we use a common trick and separate the sum into two parts: $$ \Pr(A) = \underbrace{\sum_{t=1}^{\sqrt n}\binom nt \binom{\binom t2}{3t} \frac1{n^{3t}}}_{\text{part 1}} + \underbrace{\sum_{t = \sqrt n}^{n/10} \binom nt \binom{\binom t2}{3t} \frac1{n^{3t}}}_{\text{part 2}}. $$ (The cutoff of $t = \sqrt n$ is more or less arbitrary; many others would work.)

For part $1$, we can now assume $t \le \sqrt n$ and prove a better bound of $$ \binom nt \binom{\binom t2}{3t} \frac1{n^{3t}} \le \frac1{n^t} \le \frac1n $$ and so we have a sum of $\sqrt n$ terms that are each at most $\frac1n$. These go to $0$.

For part $2$, we can use the previous bound and extend the sum to $$ \sum_{t=\sqrt n}^\infty \left(\frac1{100}\right)^t = \frac{100}{99} \cdot \frac1{100^{\sqrt n}}, $$ which also goes to $0$.