Lower degree-tail count estimate — Lemma 6.7

Every degree lies in $\{0,\dots ,n-1\}$. If $k<0$, both counts vanish. If $p=0$, every degree is zero; the threshold condition gives $k\le 0$, so either both counts vanish or both equal $n$. If $p=1$, the hypothesis $1\le c\mathrm{/}(1-c^2)$ implies $c^2+c\ge 1$, hence $c>1\mathrm{/}2$. For $n\ge 2$, $k\le (1-c)n<n-1$, so both counts vanish because every degree is $n-1$. For $n=1$, the only nonnegative admissible threshold is $k=0$, and both counts equal one. Thus the claim holds in these cases.

Now suppose $0<p<1$ and $k\ge 0$. Since $(1-c)pn<n$, the integer $k$ is at most $n-1$. For every integer $1\le i\le k$, the denominators below are positive and $i\le (1-c)pn$ gives $f_{i-1}\mathrm{/}{f}_i\le (1-c)(1-p)\mathrm{/}(1-(1-c)p)\le 1-c$. The last inequality follows from $1-p\le 1-(1-c)p$. Set $q=1-c$; then $0<q<1$. By the lower-tail bound in [F3], $\mathbb{P}(\mathrm{Bin}(n-1,p)\le k)\le f_k\mathrm{/}c$. This also covers $k=0$, when the adjacent-mass condition is empty.

By [F1] and [F2], $\mathbb{E}{X}_j=n{f}_j$ for each degree $j$. Since $X_{\le k}={\sum }_{j=0}^k{X}_j$ in the present case, finite linearity gives $\mathbb{E}{X}_{\le k}=n\mathbb{P}(\mathrm{Bin}(n-1,p)\le k)\le c^{-1}n{f}_k\le c^{-2}\mathbb{E}{X}_k$, as $0<c<1$. Together with step 1.1, this proves the claim.