Number of Isomorphic Trees

335 Views Asked by At

Given $p = cn^{−1−1/m}(1 + o(1)), m ∈ N, c > 0.$ Prove that the number of components in $G(n, p)$ isomorphic to a tree on $m + 1$ vertices converges to a $Pois$($\frac{c^m(m+1)^{m−1}} {(m+1)!}$)random variable.

What I have tried: Okay, I am not 100% sure if what I have tried is accurate but here we go... from Cayley's formula, the number of labelled trees on $k$ vertices is given by $k^{k-2}$. So let $X_{m+1}$ be the number of labelled trees. $EX_{m+1} = {n \choose m+1}*{m+1}^{m+1-2}* p^{m}$ =${n \choose m+1}*(m+1)^{m-1}* p^{m}$ $\leq$ $\frac{n^{m+1}}{m+1!}$$*(m+1)^{m-1}* p^{m}$ . After this, I applied Stirling's formula and substituted the value of $p$ into the mentioned equation but I am getting a very big messy equation and nothing is cancelling out. I have been trying to solve it for a long time now but I am not able to. Is my approach correct or I should use some other formula. But I do not see any other formulas to calculate trees except Cayley's one so I applied it. Please help me with this.

Thank you y'all.