Bounds on the Neighborhood Size of a Random Vertex in $G(n,p)$

Question

Let $G(n,p)$ be the Erdős-Rényi random graph model. I am interested in the regime $p = c/n$, where $c > 0$. Further, let $B_G(d)$ denote the neighborhood of depth $d$ of a randomly chosen vertex $u$ (i.e., the graph induced by all vertices with distance at most $d$ from $u$). Is it possible to obtain good upper bounds on the probability that the neighborhood size $|B_G(d)|$ exceeds a certain value? So far, I tried the following. The expected neighborhood size should be less than that of a Branching process with Poisson$(c )$ offspring distribution, i.e., $\mathbb{E}[|B_G(d)|] \leq c^{d+1}$. Then, I can say that, for any $\epsilon > 0$, there exists $t$, such that $\mathbb{P}(|B_G(d)| \geq t) \leq \epsilon$. Does this make sense and is it possible to obtain better bounds? Is it possible to say for example that for any fixed $t$ the probability goes to zero as $n \to \infty$? Thanks in Advance!

Answer 1

What happens as $n \to \infty$ is that for any fixed $d$, the $d$-neighbourhood of $u$ is almost surely a tree, and the distribution approaches that for the Poisson branching process. This will not be $0$ for any fixed $t$.

EDIT: If the offspring distribution for a branching process has probability generating function $\phi(s) = E[s^Y]$ (where $Y$ is the number of offspring of an individual), then the probability generating function for the size $X_n$ of $n$'th generation (with $X_0 = 1$) is $\phi_n(s)$ where $\phi_0(s) = 1$ and $\phi_{n+1}(s) = \phi_n(\phi(s))$, i.e. $\phi_n$ is the $n$-fold iterate of $\phi$.

If $Y$ has mean $\mu$ and standard deviation $\sigma$, then the mean and standard deviation of $X_n$ are $\mu_n$ and $\sigma_n$ where $\mu_n = \phi_n'(1) = \mu^n$, while if I'm not mistaken $$\sigma_n^2 = \sigma^2 \dfrac{\mu^k - \mu^{2k}}{\mu - \mu^2} = \sigma^2 \mu^{k-1}(1 + \mu + \ldots + \mu^{k-1})$$