Let $\frac{0.35\text{log}n}{n} \leq p \leq \frac{2\text{log}n}{n}$. Show that w.h.p there does not exist a tree on at most 30 vertices spanning 3 vertices of degree at most $10^{-5}\text{log}n$ in $G_{n,p}$.
I’d like to ask for some checking of the initial expression that I’d need to estimate. Let $T$ be a tree on at most 30 vertices spanning 3 vertices of degree at most $10^{-5}\text{log}n$ in $G_{n,p}$, $\mathbb{P}(T)$ the probability that it appears in $G_{n,p}$. I want to show that $\mathbb{P}(T) = o(1)$, by using Markov’s inequality:
$$\mathbb{P}(T) \leq \mathbb{E}(T) \leq {n \choose 30} 30^{28} p^{29} (1-p)^{{30 \choose 2} - 29} {30 \choose 3} p^{10^{-5}\text{log}n}$$
- ${n \choose 30}$ is the number of subsets of $[n]$ that can be used to form the trees.
- For each of those sets, there are $30^{28}$ possible trees, by Cayley’s formula.
- For each tree, we need exactly $29$ edges, hence $p^{29}$ and $(1-p)^{{30 \choose 2} - 29}$.
- For each tree, we also need to select $3$ vertices of the required degree, hence the numbers ${30 \choose 3}$ and $p^{10^{-5}\text{log}n}$.
Usually, for estimation like this one, I’d try to get a fraction with the denominator tending to infinity faster than the nominator (which in this case is $n^{30}$, after some calculations). Is there a general way or tips to do this?