# The maximum size of an induced forest
in the binomial random graph

Akhmejanova Margarita 111Computer, Electrical and Mathematical Sciences and
Engineering Division, King Abdullah University of Science and Technology
(KAUST), Thuwal 23955-6900, Saudi Arabia<EMAIL_ADDRESS>Vladislav Kozhevnikov 222Moscow Institute of Physics and Technology,
Laboratory of Combinatorial and Geometric Structures, Dolgoprudny, Russia,
<EMAIL_ADDRESS>
###### Abstract

The celebrated Frieze’s result about the independence number of $G(n,p)$
states that it is concentrated in an interval of size $o(1/p)$ for all
$C_{\varepsilon}/n<p=o(1)$. We show concentration in an interval of size
$o(1/p)$ for the maximum size (number of vertices) of an induced forest in
$G(n,p)$ for all $C_{\varepsilon}/n<p<1-\varepsilon$. Presumably, it is the
first generalization of Frieze’s result to another class of induced subgraphs
for such a range of $p$.

##  1 Introduction

For a graph $G$, we denote the maximum number of vertices in its induced
forest and tree by $F(G)$ and $T(G)$, respectively. Here, we prove the
following result.

###### Theorem 1

Let $p=p(n)\in(0,1)$, $q=1/(1-p)$. Then for any fixed $\varepsilon>0$, there
exists a sufficiently large constant $C_{\varepsilon}>0$ such that if
$C_{\varepsilon}/n<p<1-\varepsilon$, then a.a.s. (asymptotically almost
surely)

$\left\lfloor 2\log_{q}(enp(1-\varepsilon))+3\right\rfloor\leq
F(G(n,p))\leq\left\lceil 2\log_{q}(enp(1+\varepsilon))+3\right\rceil,$

i.e. $F(G(n,p))$ is concentrated in the interval of size $o(1/p)$.

The theorem is similar to the analogous theorem for independent sets given in
[7]. It refines the estimate of the deviation of the size of the largest
induced forest from its asymptotic value, which is already known [9]. The
larger the value of $p$, the better estimate is given by the theorem. In the
extreme case of $p=\operatorname{const}$ it gives the concentration of the
size in three points. The proof leverages a combination of the second moment
method and Talagrand’s inequality.

The study of induced trees in $G(n,p)$ was initiated by Erdős and Palka [6].
They showed that if $p=\operatorname{const}$, then for every $\varepsilon>0$
a.a.s.

$(2-\varepsilon)\log_{q}np\leq T(G(n,p))\leq(2+\varepsilon)\log_{q}np.$

Fernandez de la Vega [4] considered the case where the average degree is
constant. He proved that a.a.s. such graphs
($G(n,p=\frac{C}{n}),C=\operatorname{const}$) have induced trees of size
linear in $n$. This result was also independently verified by Frieze and
Jackson [8], Kučera and Rödl [13], and Łuczak and Palka [11]. Later Fernandez
de la Vega revisited the case $G\left(n,p=\frac{C}{n}\right)$ in [5] and
proved, in his own words, "nearly best possible" result for large constant $C$
and any fixed $\varepsilon>0$:

$\frac{2n(\ln C-\ln\ln C-1)}{C}\leq T(G(n,p))\leq\frac{(1+\varepsilon)2n\ln
C}{C}.$

In [16], Palka and Ruciński considered the case $p=\frac{C\ln n}{n},C>e$, for
which they established that for any fixed $\varepsilon>0$ a.a.s.

$\left(1/C-\varepsilon\right)\frac{n(\ln\ln n)}{\ln n}\leq
T(G(n,p))\leq\left(2/C+\varepsilon\right)\frac{n(\ln\ln n)}{\ln n}.$

In 2018, Dutta and Subramanian [3] for $p\geq n^{-1/2}(\ln n)^{2}$ proved that
a.a.s

$T(G)=2\left(\log_{q}np\right)+O(1/\ln q).$

It is worth mentioning that the range of $p$ is crucial. For example, for
$n^{-2/3+\varepsilon}<p<1/\ln^{2}n$ an independence number of $G(n,p)$ has
already become concentrated on two values, as seen in the recent result of
Bohman and Hofstad [1]. We also mention that for the case
$p=\operatorname{const}$, 2-point concentration results for $T(G)$ and $F(G)$
were achieved by Kamaldinov, Skorkin, Zhukovskii [12] and Krivoshapko,
Zhukovskii [14], respectively. Also recently, Draganić, Glock and Krivelevich
[2] proved that for any $\varepsilon>0$, there exists $C_{\varepsilon}>0$ such
that a.a.s. $G(n,p)$ contains an induced linear forest ( a forest with a
maximum degree of at most $2$) of size at least $(2-\varepsilon)\log_{q}(np)$
and components of size $(np)^{1/2}/(\ln np)^{4}$ whenever
$C_{\varepsilon}/n\leq p\leq n^{-1/2}(\ln n)^{2}$.

##  2 Induced forests in random graphs

Let $p=p(n)\in(0,1)$ be arbitrary, $q:=1/(1-p)$. Let $X_{k}$ be the number of
induced rooted subforests in $G(n,p)$ on $k$ vertices. Then
$F(G(n,p))=\max\left\\{k\in\left[1,n\right]\colon X_{k}>0\right\\}$.

###### Lemma 1

$\displaystyle\operatorname{E}\\!\left(X_{k}\right)$
$\displaystyle=\binom{n}{k}q^{-\binom{k}{2}}(kpq+1)^{k-1}$ (1)
$\displaystyle=\left(enpq^{-\frac{k-3}{2}}\exp\left(O\left(\frac{k/n}{(1-k/n)^{2}}\right)+O\left(\frac{\ln{k}}{k}\right)+O\left(\frac{1}{kp}\right)\right)\right)^{k}.$

Proof. Using the expression for the number of labelled rooted forests (see
[15], formula (3.4)), we obtain

$\displaystyle\operatorname{E}\\!\left(X_{k}\right)$
$\displaystyle=\binom{n}{k}\sum\limits_{m=1}^{k}\binom{k-1}{m-1}k^{k-m}p^{k-m}(1-p)^{\binom{k}{2}-(k-m)}$
$\displaystyle=\binom{n}{k}q^{-\binom{k}{2}}\sum\limits_{m=1}^{k}\binom{k-1}{m-1}(kpq)^{k-m}$
$\displaystyle=\binom{n}{k}q^{-\binom{k}{2}}(kpq+1)^{k-1}.$

Applying Stirling’s formula, we obtain

$\displaystyle\binom{n}{k}=\left(\frac{en}{k}\exp\left(O\left(\frac{k/n}{(1-k/n)^{2}}\right)+O\left(\frac{\ln{k}}{k}\right)\right)\right)^{k}$
(2)

and

$\displaystyle\operatorname{E}\\!\left(X_{k}\right)$
$\displaystyle=\left(\frac{en}{k}\exp\left(O\left(\frac{k/n}{(1-k/n)^{2}}\right)+O\left(\frac{\ln{k}}{k}\right)\right)q^{-\frac{k-1}{2}}(kpq+1)^{1-1/k}\right)^{k}$
$\displaystyle=\left(enpq^{-\frac{k-3}{2}}\exp\left(O\left(\frac{k/n}{(1-k/n)^{2}}\right)+O\left(\frac{2\ln{k}}{k}\right)+O\left(\frac{1}{kp}\right)\right)\right)^{k}.$

$\Box$

Now, for constant $\varepsilon>0$, let

$\displaystyle k_{+\varepsilon}$ $\displaystyle:=\left\lceil
2\log_{q}(enp(1+\varepsilon))+3\right\rceil,$ $\displaystyle k_{-\varepsilon}$
$\displaystyle:=\left\lfloor 2\log_{q}(enp(1-\varepsilon))+3\right\rfloor.$

###### Lemma 2

For any fixed $\varepsilon>0$ there exists a sufficiently large constant
$C_{\varepsilon}>0$ such that if $C_{\varepsilon}/n<p<1-\varepsilon$, then
$\operatorname{E}\\!\left(X_{k_{+\varepsilon}}\right)\to 0$ and
$\operatorname{E}\\!\left(X_{k_{-\varepsilon}}\right)\to+\infty$.

Proof. It is easy to see that if $C_{\varepsilon}/n<p<1-\varepsilon$ and
$C_{\varepsilon}$ is sufficiently large, then

$\begin{gathered}\frac{k_{\pm\varepsilon}}{n}\leq\frac{2\ln(np)+7}{np}\leq\frac{3\ln{C_{\varepsilon}}}{C_{\varepsilon}},\\\
k_{\pm\varepsilon}p\geq
2(1-p)\ln(np(1-\varepsilon))>2\varepsilon\ln(C_{\varepsilon}(1-\varepsilon))>\varepsilon\ln{C_{\varepsilon}},\\\
k_{\pm\varepsilon}\to+\infty,\end{gathered}$

and therefore (again, if $C_{\varepsilon}$ is sufficiently large)

$\left\lvert\exp\left(O\left(\frac{k_{\pm\varepsilon}/n}{(1-k_{\pm\varepsilon}/n)^{2}}\right)+O\left(\frac{\ln{k_{\pm\varepsilon}}}{k_{\pm\varepsilon}}\right)+O\left(\frac{1}{k_{\pm\varepsilon}p}\right)\right)-1\right\rvert\leq\frac{\varepsilon}{2}$

and

$\displaystyle\operatorname{E}\\!\left(X_{k_{+\varepsilon}}\right)$
$\displaystyle\leq\left(enpq^{-\frac{k_{+\varepsilon}-3}{2}}(1+\varepsilon/2)\right)^{k_{+\varepsilon}}\leq\left(\frac{1+\varepsilon/2}{1+\varepsilon}\right)^{k_{+\varepsilon}}\to
0,$ $\displaystyle\operatorname{E}\\!\left(X_{k_{-\varepsilon}}\right)$
$\displaystyle\geq\left(enpq^{-\frac{k_{-\varepsilon}-3}{2}}(1-\varepsilon/2)\right)^{k_{-\varepsilon}}\geq\left(\frac{1-\varepsilon/2}{1-\varepsilon}\right)^{k_{-\varepsilon}}\to+\infty.$

$\Box$

For $x\geq 0$, $y>0$, $z>0$, $\alpha>0$, let

$g(x,y,z,\alpha):=\left(\frac{yz^{x}}{x^{\alpha}}\right)^{x}.$ (3)

Here we give an auxiliary lemma, which we will use later.

###### Lemma 3

For any $B\geq{A}\geq 0$,

$\max\limits_{A\leq{x}\leq{B}}g(x,y,z,\alpha)\leq\max\left\\{\exp\left(\frac{\alpha}{2}y^{\frac{1}{\alpha}}\right),g(A,y,z,\alpha),g(B,y,z,\alpha)\right\\}.$
(4)

If, additionally, $A\geq{y^{\frac{1}{\alpha}}}$, then

$\max\limits_{A\leq{x}\leq{B}}g(x,y,z,\alpha)\leq\max\left\\{\left(y\left(\frac{e}{A}\right)^{\alpha}\right)^{\frac{A}{2}},g(A,y,z,\alpha),g(B,y,z,\alpha)\right\\}.$
(5)

Proof. Let’s fix $y,z,\alpha$ and let $g(x):=g(x,y,z,\alpha)$. Then

$\frac{\partial}{\partial{x}}\ln{g(x)}=\frac{\partial}{\partial{x}}x(-\alpha\ln{x}+\ln{y}+x\ln{z})=\ln\left(\frac{yz^{2x}}{(ex)^{\alpha}}\right).$

Consider the equation

$\frac{\partial}{\partial{x}}\ln{g(x)}=0.$

If it has no solutions for $A\leq{x}\leq{B}$, then

$\max\limits_{A\leq{x}\leq{B}}g(x)=\max\left\\{g(A),g(B)\right\\},$

which implies both (4) and (5).

Now, assume that it has at least one solution for $A\leq{x}\leq{B}$ and denote
the set of its solutions by $\mathcal{C}$. Then, for each $x\in\mathcal{C}$:

$\ln\left(\frac{yz^{2x}}{(ex)^{\alpha}}\right)=0.$

We can rewrite it as

$\left(\frac{yz^{x}}{x^{\alpha}}\right)^{2}=y\left(\frac{e}{x}\right)^{\alpha}.$

Thus, if determine a new function $h(x)$ as

$h(x):=\left(y\left(\frac{e}{x}\right)^{\alpha}\right)^{\frac{x}{2}},$

we get that $g(x)=h(x)$ for all $x\in\mathcal{C}$. The derivative

$\frac{\partial}{\partial{x}}\ln{h(x)}=\frac{1}{2}\ln\left(\frac{y}{x^{\alpha}}\right)$

has exactly one positive zero $x_{m}=y^{\frac{1}{\alpha}}$, which is the
maximum of $h(x)$ for $x\geq 0$. Thus,

$\max\limits_{x\in\mathcal{C}}g(x)\leq\max\limits_{x\geq
0}h(x)=h(x_{m})=\exp\left(\frac{\alpha}{2}y^{\frac{1}{\alpha}}\right),$

which implies (4). If we additionally assume that $A\geq{x_{m}}$, then

$\max\limits_{x\in\mathcal{C}}g(x)\leq\max\limits_{x\geq{A}}h(x)=h(A),$

which implies (5). $\Box$

###### Lemma 4

For any fixed $\varepsilon>0$ there exists a sufficiently large constant
$C_{\varepsilon}>0$ such that if $C_{\varepsilon}/n<p<1-\varepsilon$, then

$\frac{\operatorname{Var}\\!\left(X_{k_{-\varepsilon}}\right)}{(\operatorname{E}\\!\left(X_{k_{-\varepsilon}}\right))^{2}}\leq\exp\left(O\left(\frac{(\ln{np})^{4}}{np}k_{-\varepsilon}\right)\right).$

If, additionally, $p\geq(\ln{n})^{2}/\sqrt{n}$, then

$\frac{\operatorname{Var}\\!\left(X_{k_{-\varepsilon}}\right)}{(\operatorname{E}\\!\left(X_{k_{-\varepsilon}}\right))^{2}}=o(1).$

Proof. Let $k=k_{-\varepsilon}$ and $C/n<p<1-\varepsilon$, where $C$ is some
constant, whose value will be tacitly assumed to be sufficiently large
whenever necessary throughout the proof. Then the value $C_{\varepsilon}$ can
be chosen to be the maximum assumed value of $C$. In particular, $C$ should be
large enough for the claim of Lemma 2 to hold and for $k$ to satisfy the
inequalities

$\varepsilon\ln{np}\leq kp\leq 3\ln{np}.$

Now, for $\operatorname{Var}\\!\left(X_{k}\right)$,

$\operatorname{Var}\\!\left(X_{k}\right)\leq\sum\limits_{\ell=1}^{k}{F_{\ell}},$

where $F_{\ell}$ is the expected value of the number of (ordered) pairs of
induced rooted forests of size $k$ intersecting in $\ell$ vertices. Each such
pair of forests can obtained as follows:

  * •

Choose three subsets of vertices: for given two rooted forests $F_{1},F_{2}$
sharing $l$ vertices and their common $l$ vertices,

  * •

choose an induced subgraph $F=\\{T_{1},\ldots,T_{m}\\}$, where each $T_{i}$ is
a tree size of $f_{i},$

  * •

choose a rooted forest $F_{1}$ on $k$ vertices with $h_{1}$ components,
containing the induced subgraph $F$. The number of such forests is represented
by $f(k,h_{1},\left\\{f_{1},\ldots,f_{m}\right\\})$ derived in Appendex 4.2.

  * •

choose a rooted forest $F_{2}$ on $k$ vertices with $h_{2}$ components,
containing the induced subgraph $F$.

$\displaystyle\begin{split}F_{\ell}=\,&\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\sum\limits_{m=1}^{\ell}\frac{1}{m!}\sum\limits_{f_{1},\ldots,f_{m}=1}^{+\infty}\binom{\ell}{f_{1},\ldots,f_{m}}f_{1}^{f_{1}-2}\cdot\ldots\cdot{f_{m}^{f_{m}-2}}\\\
&\sum\limits_{h_{1},h_{2}=1}^{k-\ell+m}f(k,h_{1},\left\\{f_{1},\ldots,f_{m}\right\\})\cdot{f(k,h_{2},\left\\{f_{1},\ldots,f_{m}\right\\})}\\\
&p^{2k-h_{1}-h_{2}-\ell+m}(1-p)^{2\binom{k}{2}-\binom{\ell}{2}-(2k-h_{1}-h_{2}-\ell+m)}.\end{split}$
(6)

Let us make auxiliary calculations:

$\displaystyle\sum\limits_{h=1}^{k-\ell+m}$ $\displaystyle
f(k,h,\left\\{f_{1},\ldots,f_{m}\right\\})(pq)^{-h}=$
$\displaystyle=f_{1}\cdot\ldots\cdot{f_{m}}\sum\limits_{k_{0}=0}^{k-\ell}\binom{k-\ell}{k_{0}}\ell^{k-\ell-
k_{0}}\sum\limits_{h=1}^{k_{0}+m}\binom{k_{0}+m-1}{h-1}(k-\ell)^{k_{0}+m-h}(pq)^{-h}$

Using that $\sum_{k=1}^{n}\binom{n-1}{k-1}a^{n-k}b^{k}=b(a+b)^{n-1}$, we get

$\displaystyle\begin{split}&=f_{1}\cdot\ldots\cdot{f_{m}}\sum\limits_{k_{0}=0}^{k-\ell}\binom{k-\ell}{k_{0}}\ell^{k-\ell-
k_{0}}\left(k-\ell+\frac{1}{pq}\right)^{k_{0}+m-1}\frac{1}{pq}\\\
&={f_{1}}\cdot\ldots\cdot{f_{m}}\left(k+\frac{1}{pq}\right)^{k-\ell}\left(k-\ell+\frac{1}{pq}\right)^{m-1}\frac{1}{pq},\end{split}$
(7)

$\displaystyle\begin{split}\sum\limits_{f_{1},\ldots,f_{m}=1}^{+\infty}\binom{\ell}{f_{1},\ldots,f_{m}}f_{1}^{f_{1}}\cdot\ldots\cdot{f_{m}^{f_{m}}}&\leq\sum\limits_{f_{1},\ldots,f_{m}=1}^{+\infty}\binom{\ell}{f_{1},\ldots,f_{m}}f_{1}^{f_{1}-1}\cdot\ldots\cdot{f_{m}^{f_{m}-1}}\left(\frac{\ell}{m}\right)^{m}\\\
&=m!\binom{\ell-1}{m-1}\ell^{\ell-m}\left(\frac{\ell}{m}\right)^{m}\leq\frac{\ell^{\ell+m}}{m!},\end{split}$
(8)

Now we put (2) and (8) into (6),

$\displaystyle\begin{aligned}
F_{\ell}=\,&\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\sum\limits_{m=1}^{\ell}\frac{1}{m!}\sum\limits_{f_{1},\ldots,f_{m}=1}^{+\infty}\binom{\ell}{f_{1},\ldots,f_{m}}f_{1}^{f_{1}}\cdot\ldots\cdot{f_{m}^{f_{m}}}\\\
&\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\left(k-\ell+\frac{1}{pq}\right)^{2(m-1)}(pq)^{2k-\ell+m-2}q^{\binom{\ell}{2}-2\binom{k}{2}}\leq\end{aligned}$
$\displaystyle\begin{aligned}
\phantom{F_{\ell}}\,&\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\sum\limits_{m=1}^{\ell}\frac{l^{l+m}}{(m!)^{2}}\\\
&\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\left(k-\ell+\frac{1}{pq}\right)^{2(m-1)}(pq)^{2k-\ell+m-2}q^{\binom{\ell}{2}-2\binom{k}{2}}\\\
\phantom{F_{\ell}}=\,&\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\ell^{\ell}(pq)^{2k-\ell-2}q^{\binom{\ell}{2}-2\binom{k}{2}}\\\
&\sum\limits_{m=1}^{\ell}\frac{(\ell
pq)^{m}}{(m!)^{2}}\left(k-\ell+\frac{1}{pq}\right)^{2(m-1)}\end{aligned}$
$\displaystyle\begin{aligned}
\phantom{F_{\ell}}=\,&\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\ell^{\ell}{(pq)^{2k-\ell-2}}q^{\binom{\ell}{2}-2\binom{k}{2}}\\\
&\sum\limits_{m=0}^{\ell-1}\frac{(\ell{pq})^{m+1}}{((m+1)!)^{2}}\left(k-\ell+\frac{1}{pq}\right)^{2m}.\end{aligned}$

Let’s consider the following cases:

  1. 1.

${k}-\ell\leq\left\lceil\frac{k}{\sqrt{kpq}}-\frac{1}{pq}\right\rceil$;

  2. 2.

${k}-\ell\geq\left\lceil\frac{k}{\sqrt{kpq}}-\frac{1}{pq}\right\rceil$.

1\. In this case

$\sum\limits_{m=0}^{\ell-1}\frac{1}{((m+1)!)^{2}}\left(k-\ell+\frac{1}{pq}\right)^{2m}(\ell{pq})^{m+1}\leq\exp\left(2\left(k-\ell+\frac{1}{pq}\right)\sqrt{kpq}\right),$
$\displaystyle F_{\ell}$
$\displaystyle\leq\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\ell^{\ell}{(pq)^{2k-\ell-2}}q^{\binom{\ell}{2}-2\binom{k}{2}}e^{2\left(k-\ell+\frac{1}{pq}\right)\sqrt{kpq}}$
$\displaystyle\leq\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}(kpq+1)^{2k-\ell}(pq)^{-2}q^{\binom{\ell}{2}-2\binom{k}{2}}e^{2\left(k-\ell+\frac{1}{pq}\right)\sqrt{kpq}}$
$\displaystyle=\operatorname{E}\\!\left(Y_{k}\right)\cdot\binom{k}{k-\ell}\binom{n-k}{k-\ell}(kpq+1)^{k-\ell+1}q^{-\frac{(k-\ell)(k+\ell-1)}{2}}e^{2(k-\ell)\sqrt{kpq}+\frac{2k}{\sqrt{kpq}}-2\ln(pq)}$
$\displaystyle\leq\operatorname{E}\\!\left(Y_{k}\right)\cdot\left(\frac{e^{2+2\sqrt{kpq}}kn(kpq+1)}{(k-\ell)^{2}}q^{-\frac{k+\ell-1}{2}}\right)^{k-\ell}e^{\frac{2k}{\sqrt{kpq}}+O(\ln{k})}$
$\displaystyle\leq\operatorname{E}\\!\left(Y_{k}\right)\cdot\left(\frac{e^{O(\sqrt{\ln{np}})}kn\ln{np}}{q^{k}(k-\ell)^{2}}q^{\frac{k-\ell}{2}}\right)^{k-\ell}e^{\frac{2k}{\sqrt{kpq}}+O(\ln{k})}$
$\displaystyle\leq\operatorname{E}\\!\left(Y_{k}\right)\cdot\left(\frac{kn}{(np)^{1.99}(k-\ell)^{2}}q^{\frac{k-\ell}{2}}\right)^{k-\ell}e^{\frac{2k}{\sqrt{kpq}}+O(\ln{k})}$
$\displaystyle=\operatorname{E}\\!\left(Y_{k}\right)\cdot{g(k-\ell,kn/(np)^{1.99},q^{1/2},2)}e^{\frac{2k}{\sqrt{kpq}}+O(\ln{k})},$

where in the end we used
$g(x,y,z,\alpha)=\left(\frac{yz^{x}}{x^{\alpha}}\right)^{x}$ from Lemma 3.

Since $0<k-\ell<k/\sqrt{kpq}+1$, using (4), we get

$\displaystyle g(k/\sqrt{kpq}$
$\displaystyle+1,kn/(np)^{1.99},q^{1/2},2)\leq\left(\frac{O(np)}{(np)^{1.99}}q^{O\left(\frac{k}{\sqrt{kpq}}\right)}\right)^{\frac{k}{\sqrt{kpq}}+1}<\left(\frac{1}{(np)^{0.98}}\right)^{\frac{k}{\sqrt{kpq}}+1}<1,$
$\displaystyle g(k-\ell,kn$
$\displaystyle/(np)^{1.99},q^{1/2},2)\leq\max\left\\{1,\exp\left(\sqrt{\frac{kn}{(np)^{1.99}}}\right)\right\\}<e^{\frac{k}{\sqrt{kpq}}}.$

Thus, by using Lemma 3,

$\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(Y_{k}\right)\right)^{2}}\leq\frac{e^{\frac{3k}{\sqrt{kpq}}+O(\ln{k})}}{\left(\frac{1-\varepsilon/2}{1-\varepsilon}\right)^{k}}\leq\left(1-\varepsilon/2\right)^{k},$
$\frac{\operatorname{Var}\\!\left(Y_{k}\right)}{(\operatorname{E}\\!\left(Y_{k}\right))^{2}}\leq\sum\limits_{\ell=1}^{k-\left\lceil\frac{k}{\sqrt{kpq}}-\frac{1}{pq}\right\rceil}\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(Y_{k}\right)\right)^{2}}+o(1).$

2\. In this case $\ell\leq{k}\leq\left(k-\ell+\frac{1}{pq}\right)^{2}pq$. We
apply the last bound below:

$\sum\limits_{m=0}^{\ell-1}\frac{1}{((m+1)!)^{2}}\left(k-\ell+\frac{1}{pq}\right)^{2m}(\ell{pq})^{m}\leq\frac{l^{l-1}}{l!}\sum\limits_{m=0}^{\ell-1}\frac{1}{(m+1)!}\left(k-\ell+\frac{1}{pq}\right)^{2m}({pq})^{m}\\\
\leq\frac{e^{\ell}}{\ell}\sum\limits_{m=0}^{\ell-1}\frac{1}{(m+1)!}\left(k-\ell+\frac{1}{pq}\right)^{2m}(pq)^{m}\leq\frac{e^{\ell}}{\ell}\cdot\frac{\ell}{\ell!}\left(k-\ell+\frac{1}{pq}\right)^{2\ell-2}(pq)^{\ell-1}.$
(9)

$F_{\ell}=\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\ell^{\ell}{(pq)^{2k-\ell-2}}q^{\binom{\ell}{2}-2\binom{k}{2}}\times\\\
\times\sum\limits_{m=0}^{\ell-1}\frac{(\ell{pq})^{m+1}}{((m+1)!)^{2}}\left(k-\ell+\frac{1}{pq}\right)^{2m}\\\
=\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\ell^{\ell+1}{(pq)^{2k-\ell-1}}q^{\binom{\ell}{2}-2\binom{k}{2}}\times\\\
\times\sum\limits_{m=0}^{\ell-1}\frac{(\ell{pq})^{m}}{((m+1)!)^{2}}\left(k-\ell+\frac{1}{pq}\right)^{2m}\leq$

Use bound (9),

$\displaystyle\leq\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}\ell^{\ell+1}{(pq)^{2k-\ell-1}}q^{\binom{\ell}{2}-2\binom{k}{2}}\frac{e^{\ell}}{\ell!}\left(k-\ell+\frac{1}{pq}\right)^{2\ell-2}(pq)^{\ell-1}$
$\displaystyle=\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2(k-\ell)}(pq)^{2k-2}q^{\binom{\ell}{2}-2\binom{k}{2}}\frac{(e\ell)^{\ell}}{(\ell-1)!}\left(k-\ell+\frac{1}{pq}\right)^{2\ell-2}$
$\displaystyle=\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}\left(k+\frac{1}{pq}\right)^{2k-2}(pq)^{2k-2}q^{\binom{\ell}{2}-2\binom{k}{2}}\frac{(e\ell)^{\ell}}{(\ell-1)!}\left(1-\frac{\ell}{k+\frac{1}{pq}}\right)^{2\ell-2}$
$\displaystyle\leq\binom{n}{\ell,k-\ell,k-\ell,n-2k+\ell}(kpq+1)^{2k-2}q^{\binom{\ell}{2}-2\binom{k}{2}}e^{2\ell}\ell\left(1-\frac{\ell}{k+\frac{1}{pq}}\right)^{2\ell-2}$
$\displaystyle=\left(\operatorname{E}\\!\left(Y_{k}\right)\right)^{2}\cdot\frac{\binom{k}{\ell}\binom{n-k}{k-\ell}}{\binom{n}{k}}q^{\binom{\ell}{2}}e^{2\ell}\ell\left(1-\frac{\ell}{k+\frac{1}{pq}}\right)^{2\ell-2}.$

Using (4), we infer

$\displaystyle\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(Y_{k}\right)\right)^{2}}\leq\frac{\binom{k}{\ell}\binom{n-k}{k-\ell}}{\binom{n}{k}}q^{\binom{\ell}{2}}e^{2\ell}\ell.$
(10)

Hence,

$\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(X_{k}\right)\right)^{2}}\leq\binom{k}{\ell}\frac{k!}{(k-\ell)!}\frac{\frac{(n-k)!}{(n-2k+\ell)!}}{\frac{n!}{(n-k)!}}q^{\frac{k}{2}\frac{\ell^{2}}{k}}\ell
e^{2\ell}\leq\left(\frac{ek^{2}}{\ell}\right)^{\ell}\frac{\frac{(n-k)!}{(n-2k+\ell)!}}{\frac{n!}{(n-k)!}}q^{\frac{k}{2}\frac{\ell^{2}}{k}}\ell
e^{2\ell}\\\
\leq\left(\frac{ek^{2}}{\ell}\right)^{\ell}\frac{n^{k-\ell}}{n^{k}\left(1-\frac{k}{n}\right)^{k}}(O(np))^{\frac{\ell^{2}}{k}}\ell
e^{2\ell}\leq\left(O\left(\frac{k}{n}\right)\frac{(np)^{\frac{\ell}{k}}}{\frac{\ell}{k}}\right)^{\ell}e^{\frac{k^{2}}{n-k}}\\\
=\left(g\left(\frac{\ell}{k},O\left(\frac{k}{n}\right),np,1\right)\right)^{k}e^{O\left(1+\frac{k^{2}}{n}\right)},$

where in the end we used
$g(x,y,z,\alpha)=\left(\frac{yz^{x}}{x^{\alpha}}\right)^{x}$ from Lemma 3. So,
due to Lemma 3,

$\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(X_{k}\right)\right)^{2}}\leq\left(\max\left\\{e^{O\left(\frac{k}{n}\right)},g\left(1-\frac{1}{2\sqrt{kpq}},O\left(\frac{k}{n}\right),np,1\right)\right\\}\right)^{k}e^{O\left(1+\frac{k^{2}}{n}\right)}=e^{O\left(1+\frac{k^{2}}{n}\right)},$
(11)

since

$\displaystyle
g\left(1-\frac{1}{2\sqrt{kpq}},O\left(\frac{k}{n}\right),np,1\right)$
$\displaystyle=\left(O\left(\frac{\ln{np}}{(np)^{\frac{1}{2\sqrt{kpq}}}}\right)\right)^{1-\frac{1}{2\sqrt{kpq}}}$
$\displaystyle=\exp\left(\left({1-\frac{1}{2\sqrt{kpq}}}\right)\left(\ln\ln{np}-e^{O(1)}\sqrt{\ln{np}}\right)\right)$
$\displaystyle=\exp\left(-e^{O(1)}\sqrt{\ln{np}}\right).$

Next, let’s consider two cases: $p\geq(\ln{n})^{2}/\sqrt{n}$ and
$p<(\ln{n})^{2}/\sqrt{n}$.

If $p\geq(\ln{n})^{2}/\sqrt{n}$, then $k^{2}=o(n)$. Let
$\ell_{0}:=\left\lfloor\ln{n}/\ln\ln\ln{n}\right\rfloor$. Then, for
$\ell\leq\ell_{0}$, (10) does not exceed

$\displaystyle\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(X_{k}\right)\right)^{2}}$
$\displaystyle\leq\frac{\binom{k}{\ell}\binom{n-k}{k-\ell}}{\binom{n}{k}}q^{\binom{\ell}{2}}e^{2\ell}\ell\leq$
$\displaystyle\left(\frac{k!}{(k-\ell)!}\right)^{2}\frac{\frac{(n-k)!}{(n-2k+\ell)!}}{\frac{n!}{(n-k)!}}\exp\left(\frac{\ell^{2}}{2}\ln
q+2\ell+\ln\ell+O(1)\right)\leq$
$\displaystyle\left(\frac{k!}{(k-\ell)!}\right)^{2}\frac{\frac{(n-k)!}{(n-2k+\ell)!}}{\frac{n!}{(n-k)!}}\exp\left(\frac{\ell^{2}}{2}pq+2\ell+\ln\ell+O(1)\right)\leq$
$\displaystyle
k^{2\ell}\frac{n^{k-\ell}}{n^{k}}e^{\ell(p\ln{n}+O(1))}\leq\left(\frac{O(k^{2})}{n^{1-p}}\right)^{\ell}\leq\left(\frac{O((\ln{n})^{2})}{n^{1-p}p^{2}}\right)^{\ell}.$

Since, as can be easily verified, the expression $\frac{1}{n^{1-p}p^{2}}$ is
convex w.r.t. the variable $p$,

$\displaystyle\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(X_{k}\right)\right)^{2}}\leq\left(O\left(\max\left\\{\frac{\ln^{2}n}{n^{-\frac{(\ln{n})^{2}}{\sqrt{n}}}(\ln{n})^{4}},\frac{(\ln{n})^{2}}{n^{\varepsilon}(1-\varepsilon)^{2}}\right\\}\right)\right)^{\ell}\leq\left(\frac{O(1)}{(\ln{n})^{2}}\right)^{\ell}<\left(\frac{1}{\ln{n}}\right)^{\ell}.$

For $\ell>\ell_{0}$, using (5), we get

$\displaystyle\left(g\left(\frac{\ell}{k},O\left(\frac{k}{n}\right),np,1\right)\right)^{k}$
$\displaystyle\leq\left(\max\left\\{\left(O\left(\frac{k^{2}}{n}\right)\right)^{\frac{\ell_{0}}{2k}},g\left(\frac{\ell_{0}}{k},O\left(\frac{k}{n}\right),np,1\right),g\left(1-\frac{1}{2\sqrt{kpq}},O\left(\frac{k}{n}\right),np,1\right)\right\\}\right)^{k}$
$\displaystyle\leq\max\left\\{\left(O\left(\frac{k^{2}}{n}(np)^{\frac{\ell_{0}}{k}}\right)\right)^{\ell_{0}},\exp\left(-e^{O(1)}k\sqrt{\ln{n}}\right)\right\\}$
$\displaystyle\leq\max\left\\{\left(\frac{O((\ln{np})^{2})}{n^{1-p}p^{2}}\right)^{\ell_{0}},\exp\left(-e^{O(1)}k\sqrt{\ln{n}}\right)\right\\}$
$\displaystyle\leq\max\left\\{\left(\frac{1}{\ln{n}}\right)^{\frac{\ln{n}}{\ln\ln\ln{n}}},\exp\left(-e^{O(1)}k\sqrt{\ln{n}}\right)\right\\}=o\left(\frac{1}{k}\right),$

So, bound (11) does not exceed

$\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(X_{k}\right)\right)^{2}}\leq\left(g\left(\frac{\ell}{k},O\left(\frac{k}{n}\right),np,1\right)\right)^{k}e^{O\left(1+\frac{k^{2}}{n}\right)}=o\left(\frac{1}{k}\right).$

Thus,

$\frac{\operatorname{Var}\\!\left(X_{k}\right)}{(\operatorname{E}\\!\left(X_{k}\right))^{2}}\leq\sum\limits_{\ell=1}^{k}\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(Y_{k}\right)\right)^{2}}\leq\sum\limits_{\ell=1}^{\ell_{0}}\left(\frac{1}{\ln{n}}\right)^{\ell}+k\frac{\max\limits_{\ell>\ell_{0}}F_{\ell}}{\left(\operatorname{E}\\!\left(Y_{k}\right)\right)^{2}}=o(1).$

If $p<(\ln{n})^{2}/\sqrt{n}$, then

$\frac{\ln{k}}{k(\ln{np})^{4}/np}\leq\frac{np(p\ln\ln{np}+p\ln(3/p))}{\varepsilon(\ln{np})^{5}}\leq\frac{(\ln{n})^{4}(\ln\ln{n}+\ln{n})}{\varepsilon(\frac{1}{2}\ln{n}-2\ln\ln{n})^{5}}=O(1),$
$\frac{k^{2}}{n}\leq\frac{3\ln{np}}{np}k,$
$\frac{\operatorname{Var}\\!\left(X_{k}\right)}{(\operatorname{E}\\!\left(X_{k}\right))^{2}}\leq\sum\limits_{\ell=1}^{k}\frac{F_{\ell}}{\left(\operatorname{E}\\!\left(X_{k}\right)\right)^{2}}\leq\exp\left(O\left(\frac{k^{2}}{n}\right)+O\left(\ln{k}\right)\right)\leq\exp\left(O\left(\frac{(\ln{np})^{4}}{np}k\right)\right).$

##  3 Proof of Theorem 1

The upper bound is given by Lemma 2 and the first moment method. If
$p\geq(\ln{n})^{2}/\sqrt{n}$, then the lower bound follows from Lemma 4
applied for $k=k_{-\varepsilon}$ and the second moment method.

If $p<(\ln{n})^{2}/\sqrt{n}$, then we will obtain the lower bound using
Talagrand’s inequality from [10]. For a graph $G$ on the vertex set $[n]$ with
the set of edges $\bigsqcup\limits_{i=1}^{n}x_{i}$ defined by the variables
$x_{i}\subset\left\\{\left\\{i,j\right\\}\colon
j\in\left[1,i-1\right]\right\\}$, $i\in\left[2,n\right]$, let
$\varphi(G)=\varphi(x_{2},\ldots,x_{n})$ be the size of the largest induced
forest in $G$. First, notice that $\varphi(x_{2},\ldots,x_{n})$ satisfies
Lipschitz condition. Indeed, $\varphi(x_{2},\ldots,x_{n})$ cannot decrease if
an edge is removed. On the other hand, if any number of edges incident to a
single vertex is added, $\varphi(x_{2},\ldots,x_{n})$ can decrease by at most
$1$. Secondly, notice that $\varphi(x_{2},\ldots,x_{n})$ is certifiable by the
function $\psi(r)=\left\lceil r\right\rceil$. Indeed, for any integer $r$,
there exists a certificate of size $r$ enforcing the inequality
$\varphi(x_{2},\ldots,x_{n})\geq{r}$, which is simply the set of vertices of
the corresponding largest induced forest. Thus, Talagrand’s inequality is
applicable to the random variable $F(G(n,p))=\varphi(G(n,p))$:

$\displaystyle\mathbb{P}{\left(F(G(n,p))\leq{k_{-\varepsilon}-1}\right)}\mathbb{P}{\left(F(G(n,p))\geq{k_{-\varepsilon/2}}\right)}$
$\displaystyle\leq\exp\left(-\frac{(k_{-\varepsilon/2}-k_{-\varepsilon}+1)^{2}}{4k_{-\varepsilon/2}}\right)$
$\displaystyle\leq\exp\left(-\frac{\varepsilon^{2}}{4k_{-\varepsilon/2}p^{2}}\right)$
$\displaystyle\leq\exp\left(-\frac{\varepsilon^{2}k_{-\varepsilon/2}}{40(\ln{np})^{2}}\right).$

Using Lemma 4 for $k=k_{-\varepsilon/2}$ and Paley–Zygmund inequality, we get

$\mathbb{P}{\left(F(G(n,p))\geq{k_{-\varepsilon/2}}\right)}=\mathbb{P}{\left(X_{k_{-\varepsilon/2}}>0\right)}\geq\frac{(\operatorname{E}{X_{k_{-\varepsilon/2}}})^{2}}{\operatorname{E}{X_{k_{-\varepsilon/2}}^{2}}}\geq\exp\left(-\frac{k_{-\varepsilon/2}}{(\ln{np})^{5}}\right)$

and, finally, recalling that $p<(\ln{n})^{2}/\sqrt{n}$,

$\mathbb{P}{\left(F(G(n,p))\leq{k_{-\varepsilon}-1}\right)}\leq\exp\left(\frac{k_{-\varepsilon/2}}{(\ln{np})^{5}}-\frac{\varepsilon^{2}k_{-\varepsilon/2}}{40(\ln{np})^{2}}\right)<\exp\left(-\frac{\sqrt{n}}{(\ln{n})^{4}}\right)\to
0.$

$\Box$

### Acknowledgements

The research work of Kozhevnikov is supported by Russian Science Foundation,
project 21-71- 10092. The research work of Akhmejanova is supported by King
Abdullah University of Science and Technology (KAUST). The first author is a
Young Russian Mathematics award winner (2020) and would like to thank its
sponsors and jury.

## References

  * [1] T. Bohman, J. Hofstad. Two-Point Concentration of the Independence Number of the Random Graph. _preprint_ , arXiv:2208.00117, 2022.
  * [2] N. Draganić, S. Glock, M. Krivelevich. The largest hole in sparse random graphs. _Random Structures & Algorithms_, 61(4): 666–677, 2022.
  * [3] K. Dutta, C.R. Subramanian. On Induced Paths, Holes and Trees in Random Graphs. _Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)_ , Society for Industrial and Applied Mathematics, 168–177, 2018.
  * [4] W. Fernandez de la Vega. Induced trees in sparse random graphs. _Graphs and Combinatorics_ , 2(1): 227–231, 1986.
  * [5] W. Fernandez de la Vega. The largest induced tree in a sparse random graph. _Random Structures and Algorithms_ , 9(1-2): 93–97, 1996.
  * [6] P. Erdős, Z. Palka. Trees in random graphs. _Discrete Mathematics_ , 46(2): 145–150, 1983.
  * [7] A. M. Frieze. On the independence number of random graphs. _Discrete Mathematics_ , 81(2): 171–175, 1990.
  * [8] A. M. Frieze, B. Jackson. Large induced trees in sparse random graphs. _Journal of Combinatorial Theory, Series B_ , 42(2): 181–195, 1987.
  * [9] S. Glock. Note on induced paths in sparse random graphs. _arxiv_ , 2021.
  * [10] S. Janson, T. Łuczak, A. Ruciński. Random Graphs. _John Wiley & Sons, Inc._, 2000.
  * [11] T. Łuczak, Z. Palka. Maximal induced trees in sparse random graphs. _Discrete Mathematics_ , 72(1): 257–265, 1988.
  * [12] D. Kamaldinov, A. Skorkin, M. Zhukovskii. Maximum sparse induced subgraphs of the binomial random graph with given number of edges. _Discrete Mathematics_ , 344(2): 112205, 2021.
  * [13] L. Kučera, V. Rödl. Large trees in random graphs. _Commentationes Mathematicae Universitatis Carolinae_ , 28, 1987.
  * [14] M. Zhukovskii, M. Krivoshapko. Maximum induced forests in random graphs. _Discrete Applied Mathematics_ , 305: 211–213, 2021.
  * [15] J. W. Moon. Counting labelled trees. 1970.
  * [16] Z. Palka, A. Palka, A. Ruciński. On the order of the largest induced tree in a random graph. _Discrete Applied Mathematics_ , 15: 75–83, 1986.
  * [17] A. Renyi. Some remarks on the theory of trees. _Publ. Math. Inst. Hungar. Acad. Sci._ , 4(1): 73–83, 1959.

##  4 Appendix

###  4.1 Coding trees with a fixed independent set

It is known that a labelled tree on vertices $\left[1,n\right]$ can be encoded
by a Prüfer sequence
$\left(a_{1},\ldots,a_{n-2}\right)\in\left[1,n\right]^{n-2}$. Let’s fix some
$m\in\left[1,n\right]$. Then the standard encoding procedure from [15] can be
slightly modified to encode only the trees with the independent set
$\left[1,m\right]$ by two sequences
$a=\left(a_{1},\ldots,a_{m-1}\right)\in\left[m+1,n\right]^{m-1}$ and
$b=\left(b_{1},\ldots,b_{n-m-1}\right)\in\left[1,n\right]^{n-m-1}$. Take any
such tree and successively prune it’s leaves, starting from leaves with
smallest labels, as in the standard encoding procedure, until only one edge
remains. If, however, the pruned leaf has the label in $\left[1,m\right]$,
then write the label of its neighbour to the sequence $a$, otherwise, to the
sequence $b$.

This modified encoding allows to find the number of such labelled trees on
vertices $\left[1,n\right]$ with a given degree sequence
$\left(d_{1},\ldots,d_{n}\right)$, which is exactly

$\binom{n-m-1}{d_{1}-1,d_{2}-1,\ldots,d_{m}-1,n-1-\left(d_{1}+\ldots,d_{m}\right)}\binom{n+m-2-\left(d_{1}+\ldots,d_{m}\right)}{d_{m+1}-1,\ldots,d_{n}-1}.$
(12)

From (12) it is evident that such a tree with the degree sequence
$\left(d_{1},\ldots,d_{n}\right)$ exists iff $d_{1}+\ldots+d_{n}=2n-2$ and
$d_{1}+\ldots+d_{m}\leq{n-1}$.

###  4.2 Counting forests with a fixed induced subforest

Let $K_{n}$ be the complete graph on $n$ vertices. For any $F\subset{K_{n}}$,
let’s define $f(n,h,F)$ as the number of rooted (with a distinguished vertex
in each component) spanning forests of $K_{n}$ with $h$ components containing
$F$ as an induced subgraph.

Let’s consider a forest $F\subset{K_{n}}$ with $m$ components with numbers of
vertices $f_{1},\ldots,f_{m}$ and let $l:=\left\lvert
V(F)\right\rvert=f_{1}+\ldots+f_{m}$. Each $h$-component rooted spanning
forest of $K_{n}$ containing $F$ as an induced subgraph can be uniquely
constructed as follows:

  * •

contract each component of $F$ into a single vertex;

  * •

label the contracted components by $\left[1,m\right]$ and the rest of the
vertices of $K_{n+1}$ by $\left[m+1,n-\ell+m\right]$;

  * •

add one more vertex labelled $n-\ell+m+1$;

  * •

construct a labelled tree on the vertices $\left[1,n-\ell+m+1\right]$ in which
$\deg(n-\ell+m+1)=h$;

  * •

expand the vertices $\left[1,m\right]$ (which are the contracted components);

  * •

remove the vertex labelled $n-\ell+m+1$.

Thus, applying (12),

$f(n,h,F)=\sum\limits_{d_{1},\ldots,d_{n-\ell+m}=1}^{+\infty}\binom{n-\ell}{d_{1}-1,d_{2}-1,\ldots,d_{m}-1,n-\ell+m-\left(d_{1}+\ldots,d_{m}\right)}\cdot\\\
\cdot\binom{n-\ell+2m-1-\left(d_{1}+\ldots,d_{m}\right)}{d_{m+1}-1,\ldots,d_{n-\ell+m}-1,h-1}\cdot{f_{1}^{d_{1}}\cdot\ldots\cdot{f_{m}^{d_{m}}}}\\\
=\sum\limits_{k_{0},k_{1},\ldots,k_{m}=0}^{+\infty}\binom{n-\ell}{k_{0},k_{1},\ldots,k_{m}}\cdot{f_{1}^{k_{1}+1}\cdot\ldots\cdot{f_{m}^{k_{m}+1}}}\cdot\sum\limits_{k_{m+1},\ldots,k_{n-\ell+m}=0}^{+\infty}\binom{k_{0}+m-1}{k_{m+1},\ldots,k_{n-\ell+m},h-1}\\\
=f_{1}\cdot\ldots\cdot{f_{m}}\cdot\sum\limits_{k_{0}=0}^{n-\ell}\binom{n-\ell}{k_{0}}l^{n-\ell-
k_{0}}\cdot\binom{k_{0}+m-1}{h-1}(n-\ell)^{k_{0}+m-h}$

It is easy to see that $f(n,h,F)$ depends only on the sizes of the components
of $F$. Therefore, we can define

$f(k,h,\left\\{f_{1},\ldots,f_{m}\right\\}):=f(k,h,F).$

Thus,

$f(k,h,\left\\{f_{1},\ldots,f_{m}\right\\})=f_{1}\cdot\ldots\cdot{f_{m}}\sum\limits_{k_{0}=0}^{k-\ell}\binom{k-\ell}{k_{0}}\ell^{k-\ell-
k_{0}}\cdot\binom{k_{0}+m-1}{h-1}(k-\ell)^{k_{0}+m-h}.$ (13)