1 Introduction
We ask the following natural question: given a graph H and a natural number n, what are the possible values of m such that there exists a graph on n vertices with exactly m copies of H? Surprisingly, very little is known about this problem.
A question of this flavour was considered by Kittipassorn and Mészáros [Reference Kittipassorn and Mészáros9] who studied the set
$F_{n}$
of the possible number of frustrated triangles, that is, triples of vertices inducing an odd number of edges. They proved that about two thirds of the numbers in
$[ 0, n^{3/2} ]$
do not appear in
$F_{n}$
and that every even number between
$(1+o(1))n^{3/2}$
and
$\binom {n}{3}-(1+o(1))n^{3/2}$
is a member of
$F_{n}$
for sufficiently large even n.
Much more attention has been given to the problem of maximising or minimising the number of subgraphs of certain types of graphs with a given number of vertices and edges. For example, Rademacher proved that every graph with
$\lfloor n^2/4 \rfloor + 1$
edges contains at least
$\lfloor n/2 \rfloor $
triangles. Erdős [Reference Erdős5] posed a conjecture, which was later proved by Lovász and Simonovits [Reference Lovász, Simonovits, Erdős, Alpár, Halász and Sárközy11], that a graph of size
$\lfloor n^2/4\rfloor + k$
contains at least
$k\lfloor n/2 \rfloor $
triangles if
$k < n/2$
. On the other hand, Alon [Reference Alon1] investigated the maximum number of subgraphs isomorphic to some given graph, where the maximum is taken over all graphs of a certain size. We refer to [Reference Cutler and Radcliffe3, Reference Erdős4, 6–8, Reference Larman10, Reference Nikiforov12, Reference Nordhaus and Stewart13] for related results.
We consider a fixed connected graph H. For a graph G, we define
$k_{H}(G)$
to be the number of copies of H in G. The main object of interest of this paper is
$$ \begin{align*} S^{(n)}_{H} = \{ k_{H}(G) : |G| = n \}, \end{align*} $$
the set of the possible number of copies of H in a graph on n vertices. Our first result says that almost every number (in the appropriate range) is realisable as a number of copies of H in some graph of order n.
Theorem 1.1.
$[0, (1-o(1))k_{H}(K_{n})] \subset S^{(n)}_{H}$
as
$n \rightarrow \infty $
.
It is not unreasonable to expect that
$o(1)$
above could be replaced by
$0$
. As it happens, this is not the case. Before we state the second result, we introduce some notation that plays a major role in the rest of the paper. For a graph
$G = (V, E)$
of order n, let
$f_{H}(G)$
be the number of subgraphs F of
$K(V)$
isomorphic to H such that
$E(F) \cap E \neq \emptyset $
, where
$K(V)$
denotes the complete graph on the vertex set V. For example,
$f_{K_{3}}(G)$
is the number of triples of vertices in G inducing at least one edge. Observe that
$k_{H}(G) = k_{H}(K_{n}) - f_{H}(\overline {G})$
, and therefore we work instead with the complement of G which is easier to draw when G is dense. We write
$a_{H}^{(n)}(t) = f_{H}(S_{t}^{(n)})$
and
$b_{H}^{(n)}(t) = f_{H}(M_{t}^{(n)})$
, where
$S_{t}^{(n)}$
is a graph on n vertices with t edges forming a star with
$t \le n-1$
and
$M_{t}^{(n)}$
is a graph on n vertices with t edges forming a matching with
$t \le \lfloor n/2 \rfloor $
. We prove the existence of some gaps in
$S_{H}^{(n)}$
.
Theorem 1.2. For all sufficiently large n and all
$t \ge 0$
,
$$ \begin{align*} | ( k_{H}(K_{n})-a^{(n)}_{H}(t+1), k_{H}(K_{n})-b_{H}^{(n)}(t) ) \cap S^{(n)}_{H} | = o(n^{h-2}). \end{align*} $$
In particular, there exists a number
$m = k_{H}(K_n) - (c_H + o(1))n^{h-{3}/{2}}$
that is not a member of
$S_{H}^{(n)}$
for some constant
$c_H$
.
In Section 4, we see that, when
$t < c\sqrt {n}$
, where c is some nonnegative constant depending only on H, the length of the interval
$a_{H}^{(n)}(t+1) - b_{H}^{(n)}(t)$
is of order
$n^{h-2}$
. When H is a triangle, we prove sharp analogues of Theorems 1.1 and 1.2.
Theorem 1.3. We have:
-
(i)
$[0, \binom {n}{3}-(\sqrt {2}+o(1))n^{3/2}] \subset S_{K_{3}}^{(n)}$
as
$n \rightarrow \infty $
; and -
(ii)
$(\binom {n}{3} - a_{K_{3}}^{(n)}(t+1), \binom {n}{3} - b_{K_{3}}^{(n)}(t)) \cap S_{K_{3}}^{(n)} = \emptyset $
for all
$n,t \ge 0$
.
We see that
$a_{K_{3}}^{(n)}(t) = t(n-2)-\binom {t}{2}$
and
$b_{K_{3}}^{(n)}(t) = t(n-2)$
, so it is easy to check that the interval in the second part of the theorem is not empty as long as
$t \lesssim \sqrt {2n}$
. Thus, there exists a number
$m = \binom {n}{3}-( \sqrt {2} +o(1))n^{3/2}$
that is not a member of
$T_{n}$
. Therefore, the first part of Theorem 1.3 is sharp.
The same idea that we use in the case of triangles also works for cherries, that is, paths with two edges,
$P_{2}$
.
Theorem 1.4. We have:
-
(i)
$[0, 3\binom {n}{3}-(4+o(1))n^{3/2}] \subset S_{P_{2}}^{(n)}$
as
$n \rightarrow \infty $
; and -
(ii)
$(3\binom {n}{3} - a_{P_{2}}^{(n)}(t+1), 3\binom {n}{3} - b_{P_{2}}^{(n)}(t)) \cap S_{P_{2}}^{(n)} = \emptyset $
for all
$n,t \ge 0$
.
As in the case of triangles, the first part of Theorem 1.4 is sharp.
The rest of this paper is organised as follows. In Section 2, we prove some preliminary lemmas. We prove the sharp results for triangles (Theorem 1.3) in Section 3. The proofs of Theorems 1.1 and 1.2 are presented in Section 4. We conclude the paper in Section 5 with some open problems.
2 Complete graphs
In this section, we consider the case when
$H = K_{r}$
is a complete graph and prove some lemmas that we use to prove our main theorems.
We start by showing that the first
$(\lfloor {(n-r^2)}/{r}\rfloor )^{r}$
natural numbers are realisable: that is, for every
$k \le (\lfloor {(n-r^2)}/{r}\rfloor )^{r}$
, there exists an r-partite graph on n vertices with exactly k copies of
$K_{r}$
.
Lemma 2.1. For natural numbers
$n,r$
with
$n \ge r \ge 2$
, and any nonnegative integer
$k \le (\lfloor {(n-r^2)}/{r} \rfloor )^{r}$
, there is an r-partite graph with k copies of
$K_{r}$
.
Proof. Let
$P_{n,r}$
be the set of the possible number of copies of
$K_{r}$
in an r-partite graph on n vertices. Clearly,
$P_{n,r} \subseteq S^{(n)}_{K_{r}}$
.
We use induction on r. The base case
$r = 2$
is trivial. Suppose that the assertion holds for some
$r \ge 2$
. Let
$G = ( V_{1} \sqcup V_{2} \sqcup V_{3}, E )$
, where
$|V_{1}| = \lceil {r(n-r)}/{(r+1)}\rceil $
,
$|V_{2}| = \lfloor {(n-r)}/{(r+1)}\rfloor $
, every vertex in
$V_{1}$
is joined to every vertex in
$V_{2}$
, and
$V_{3}$
induces a
$K_{r}$
. By the induction hypothesis, we can replace
$V_{1}$
by an r-partite graph having k copies of
$K_{r}$
, and therefore we obtain an
$(r+1)$
-partite graph having
$\lfloor {(n-r)}/{(r+1)}\rfloor k$
copies of
$K_{r+1}$
, for any
$$ \begin{align*}k \le \bigg( \bigg\lfloor\frac{\frac{r(n-r)}{r+1}-r^{2}}{r}\bigg\rfloor \bigg) ^{r} = \bigg( \bigg\lfloor\frac{n-r}{r+1}-r\bigg\rfloor \bigg)^{r}.\end{align*} $$
Therefore, we get an increasing sequence in
$P_{n, r+1}$
, starting with
$0$
and ending with
$$ \begin{align*}\bigg\lfloor\frac{n-r}{r+1}\bigg\rfloor\bigg( \bigg\lfloor\frac{n-r}{r+1} -r\bigg\rfloor \bigg)^{r} \ge \bigg( \bigg\lfloor\frac{n-r}{r+1}-r\bigg\rfloor \bigg)^{r+1} = \bigg( \bigg\lfloor\frac{n-r(r+2)}{r+1}\bigg\rfloor \bigg)^{r+1} \ge \bigg(\bigg\lfloor \frac{n-(r+1)^{2}}{r+1}\bigg\rfloor \bigg)^{r+1},\end{align*} $$
such that the difference between consecutive terms is equal to
$|V_{2}|$
. To obtain the missing numbers between consecutive terms, notice that it is enough to join the needed number of vertices in
$V_{2}$
to every vertex in
$V_{3}$
. Clearly, all graphs in the sequence are
$(r+1)$
-partite.
Recall that
$f_{H}(G)$
is the number of subgraphs F of
$K(V)$
isomorphic to H such that
$E(F) \cap E \neq \emptyset $
, where
$K(V)$
denotes the complete graph on the vertex set V. Moreover,
$a_{H}^{(n)}(t) = f_{H}(S_{t}^{(n)})$
and
$b_{H}^{(n)}(t) = f_{H}(M_{t}^{(n)})$
, where
$S_{t}^{(n)}$
is a graph on n vertices with t edges forming a star and
$M_{t}^{(n)}$
is a graph on n vertices with t edges forming a matching.
We fix
$n, r \ge 2$
and, for brevity, write
$f(G) = f_{K_{r}}(G)$
,
$a_{t} = a_{K_{r}}^{(n)}(t)$
,
$b_{t} = b_{K_{r}}^{(n)}(t)$
. Recall that the number of copies of
$K_{r}$
in G is equal to
$\binom {n}{r} - f(\overline {G})$
, where
$f(G)$
is the number of r-sets of vertices in G that induce at least one edge. Therefore, we work instead with the complement of G, which is easier to deal with when G is dense. Observe that
$a_{t} = \sum _{i=1}^{t}\binom {n-1-i}{r-2}$
and hence
$a_{t+1} - a_{t} = \binom {n-1-(t+1)}{r-2}$
.
Lemma 2.2. For a graph G on n vertices and
$e \le \tfrac 12(n-1)$
edges,
$f(G) \in [ a_{e}, b_{e} ]$
.
Proof. We show this by induction on the number of edges e. In the base case when
$e \le 1$
, there is nothing to show. For
$e> 1$
, assume that
$f(G') \in [a_{e-1}, b_{e-1}]$
for any graph
$G'$
on n vertices and
$e - 1$
edges.
First, we show that
$f(G) \le b_{e}$
. Take an edge
$xy \in G$
such that
$d(y)> 1$
and an isolated vertex
$w \in G$
. Let
$G'$
be a graph obtained by removing
$xy$
from G and replacing it by
$xw$
. Note that
$f(G') \ge f(G)$
. By repeating this process for any nonindependent edge, we eventually obtain a matching, since
$e \le \tfrac 12(n-1)$
, without decreasing the value of f.
To show that
$f(G) \ge a_{e}$
, pick an edge
$xy \in G$
and let
$G'$
be a graph obtained by removing
$xy$
from G. We show that
$f(G) - f(G') \ge \binom {n-1-e}{r-2} = a_{e} - a_{e-1}$
, which completes the proof, as then
$f(G) \ge f(G') + a_{e} - a_{e-1} \ge a_{e}$
, by the induction hypothesis applied to
$G'$
. Let
$A = V(G) \backslash (N_{G}(x) \cup N_{G}(y) )$
(observe that
$x, y \neq A$
). Write M for a largest independent set contained in A and write
$e_{A}$
for the number of edges induced by A. By deleting an endpoint of each edge in A, we see that
$|M| \ge |A| - e_{A}$
. Therefore,
$$ \begin{align*} f(G) - f(G') \ge \binom{|M|}{r-2} \ge \binom{n - |N(x) \cup N(y)|-e_{A}}{r-2} \ge \binom{n-e-1}{r-2}.\\[-42pt] \end{align*} $$
We remark that Lemma 2.2 does not imply that
$f(G) \notin (b_{t}, a_{t+1})$
for any t. However, the result follows immediately from the monotonicity of f.
Lemma 2.3. For any graph G on n vertices and any
$t \ge 0$
,
$f(G) \notin ( b_{t}, a_{t+1} )$
.
Proof. Write
$t_{\max } = \max \{t: b_{t-1} +1 < a_{t} \}$
for the last t where there is a gap between the intervals
$[ a_{t-1},b_{t-1} ]$
and
$[ a_{t}, b_{t} ]$
. It is enough to show that
$f(G) \in [ a_{t}, b_{t} ]$
for some
$t \le t_{\max }$
or
$f(G) \ge a_{t_{\max }}$
. This follows from Lemma 2.2 if
$e(G) \le t_{\max }$
. So we can assume that
$e(G)> t_{\max }$
. Let
$G'$
be a graph obtained from G by deleting some edges until there are exactly
$t_{\max }$
edges left. By the monotonicity of f and Lemma 2.2,
$f(G) \ge f(G') \ge a_{t_{\max }}$
.
We remark that
$t_{\max } = \Theta (\sqrt {n})$
.
We now turn our attention to the problem of determining which numbers can be expressed as a restricted sum of binomials. More precisely, we are interested in the set,
$A_{k}$
, of integers that can be expressed as
$\sum _{i=1}^{j}\binom {d_{i}}{2}$
, where
$\sum _{i=1}^{j}d_{i} = k$
and each
$d_{i}$
is a positive integer. Let
$s_{k}$
be the largest integer such that any integer between
$0$
and
$s_{k}$
belongs to
$A_{k}$
. To the best of our knowledge, this sequence was first studied by Dogan (see [Reference Balister and Dogan2, Lemma 20]) who showed that
$s_{k} \ge \tfrac 12(k - 2\sqrt {k})^{2}$
. Here, we present a simpler proof of an asymptotically stronger result of this kind. We start with a simple observation.
Observation 2.4. Let
$z_{k}$
be an increasing sequence such that
$s_k \geq z_k>0$
for every k. For any positive integer k, we have
$s_{k} \geq \binom {k^{*}}{2}$
, where
$k^{*}$
is the smallest nonnegative integer such that
$z_{k-k^{*}} < k^{*}$
.
Proof. Take any
$\ell \leq \binom {k^{*}}{2}$
. We show that
$\ell $
can be written as a restricted sum of binomials. When
$\ell = \binom {k^{*}}{2}$
, there is nothing to show, so we can assume that
$\ell < \binom {k^{*}}{2}$
. Let
$k'$
be the largest integer such that
$\binom {k'}{2} \leq \ell $
. Write
$\ell '$
for
$\ell - \binom {k'}{2}$
and observe that
$\ell ' = \ell -\binom {k'}{2} < \binom {k'+1}{2}-\binom {k'}{2} = k' < k^{*}$
. By the definition of
$k^{*}$
,
$s_{k-k'} \ge z_{k-k'} \geq k'> \ell '$
, and the result follows from the definition of
$s_{k-k'}$
.
We obtain a lower bound for
$s_k$
by applying Observation 2.4 several times.
Lemma 2.5.
$s_{k} \geq \tfrac 12(k-\sqrt {2k})^2 + O(k)$
as
$k\to \infty $
.
Proof. First,
$s_{k} \geq \lfloor {k}/{2} \rfloor $
, as we can write any
$\ell \leq \lfloor {k}/{2} \rfloor $
as
$\sum _{i=1}^{\ell }\binom {2}{2} + \sum _{i=1}^{k - 2\ell }\binom {1}{2}$
. For every
$k' \leq \lfloor k/3 \rfloor $
, we have
$\lfloor {(k-k')}/{2} \rfloor \geq k'$
; therefore,
$s_{k} \geq \binom {\lfloor k/3 \rfloor }{2}$
by Observation 2.4. Applying Observation 2.4 again yields
$s_{k} \geq \binom {k - 3\sqrt {2k}}{2}$
, and by applying it one more time, we arrive at the statement of the lemma.
3 Triangles
We now consider the case when
$H = K_{3}$
, that is, when H is a triangle. For brevity, we write
$T_{n} = S^{(n)}_{K_{3}}$
,
$f(G) = f_{K_{3}}(G)$
,
$a_{t} = a^{(n)}_{K_{3}}(t)$
and
$b_{t} = b^{(n)}_{K_{3}}(t)$
in this section.
Before we improve Lemma 2.1 to Theorem 1.3(i), we consider Theorem 1.3(ii) and look for nonmembers of
$T_{n}$
. Recall that the number of triangles in G is equal to
$\binom {n}{3} - f(\overline {G})$
, where
$f(G)$
is the number of triples of vertices in G that induce at least one edge. Notice that we have a simple formula,
$f(G) = e(G)(n-2) - n_{c} + n_{t}$
, where
$n_{c}$
is the number of cherries (that is, paths with two edges,
$P_{2}$
) and
$n_t$
is the number of triangles in G. This comes from the fact that each edge is contained in exactly
$n-2$
triples, but we double or triple count the triples which contain more than one edge. Using this formula, it is easy to see that
$a_{t} = t(n-2) - \binom {t}{2}$
and
$b_{t} = t(n-2)$
.
We showed in Lemma 2.3 that
$f(G) \not \in ( b_{t}, a_{t+1} )$
for all
$t \ge 0$
. On the other hand, we now prove that every number bigger than
$( \sqrt {2} + o(1) )n^{3/2}$
is realisable.
Observe that if G is triangle-free, then
$$ \begin{align*} f(G) &= e(G)(n-2) - n_{c} = e(G)(n-2) - \sum_{x \in G} \binom{d(x)}{2}. \end{align*} $$
Lemma 3.1. Let k be such that
$s_{k} \ge n -2$
and
$2k \le n$
. For every m in the interval
$[ k(n-2), \binom {n-2k}{3} + k(n-2)]$
, there is a graph G on n vertices such that
$f(G) = m$
.
Proof. Take any
$m \in [ k(n-2), \binom {n-2k}{3} + k(n-2)]$
. We construct a graph G on the vertex set
$U \sqcup V$
, where
$|U| = n -2k$
,
$|V| = 2k$
, such that
$f(G) = m$
. Observe, first, that since adding an edge to a graph increases the value of f by at most
${n-2}$
, we can find a configuration of edges in U that contributes
$m'$
to f, where
${0 \le m' + k(n-2) - m < n -2}$
. We now find a configuration of edges in V that contributes exactly
$m'-m$
to f. By the definition of
$s_{k}$
, we can find a sequence of positive integers
$d_{1},d_{2}, \ldots , d_{j}$
which sum up to k and such that
$\sum _{i=1}^{j} \binom {d_{i}}{2} = m' + k(n-2) - m$
. Let
$G[V]$
be the union of stars
$S_{d_1}, S_{d_2}, \ldots , S_{d_j}$
and an independent set. Then
$f(G) = m' + k(n-2) - (m' + k(n-2) - m) = m$
.
Corollary 3.2. For any sufficiently large n, if
$m \in [\sqrt {2}n^{3/2} + 4n^{5/4}, (1-o(1))\binom {n}{3} ]$
, then there is a graph G on n vertices such that
$f(G) = m$
.
Proof. It follows from Lemma 2.5 that
$s_{k} \geq \binom {k - \sqrt {2k}}{2}$
, and hence, if
$k \geq \sqrt {2n} + 4 n^{1/4}$
, then
$s_k \geq n-2$
for sufficiently large n. The rest follows from Lemma 3.1.
We are now ready to deduce Theorem 1.3 from Lemmas 2.1, 2.3 and Corollary 3.2.
Proof of Theorem 1.3.
(i) Recall that the number of triangles in G is
$\binom {n}{3} - f(\overline {G})$
. Therefore, Corollary 3.2 implies that
$[o(\binom {n}{3}), \binom {n}{3}-(\sqrt {2}+o(1))n^{3/2}] \subset T_{n}$
. Together with Lemma 2.1, which, for
$r = 3$
, says that
$[0, ( {(n-9)}/{3} )^{3} ] \subset T_{n}$
, we conclude that
$[ 0, \binom {n}{3} - ( \sqrt {2} + o(1) )n^{3/2} ] \subseteq T_{n}$
for sufficiently large n.
(ii) Since the number of triangles in G is equal to
$\binom {n}{3} - f(\overline {G})$
, we obtain, using Lemma 2.3, that
$(\binom {n}{3} - a_{t+1}, \binom {n}{3} - b_{t}) \cap T_{n} = \emptyset $
for all
$n,t \ge 0$
.
4 General H
Now, we consider the case when H is an arbitrary connected graph on
$h \ge 3$
vertices. We start by showing that the first
$(1-o(1))k_{H}(K_{n})$
numbers are realisable when n goes to infinity.
Our strategy is to recursively partition the vertex set into two subsets and modify the edges between vertices in each of the classes, but without adding edges between the classes. Let
$g_{H} = g_{H}^{(n)}$
be the maximum number of new copies of H obtained by adding an edge to a graph, over all graphs on n vertices. We claim that there is a constant
$c_{H}> 0$
such that
$g_{H} \le c_{H}n^{h-2}$
. Indeed, a new copy must contain both of the end vertices of the newly added edge, there are
$\binom {n-2}{h-2}\ h$
-sets of vertices in G containing two fixed vertices and each h-set may contain at most
$h!$
copies of H. Therefore,
${g_{H} \le h!\binom {n-2}{h-2} \le c_{H}n^{h-2}}$
.
The next two lemmas are needed in our construction.
Lemma 4.1. If
$[0, cn^{\alpha }] \subset S^{(n)}_{H}$
for all sufficiently large n, where
$\alpha \le h-2$
, then, for all sufficiently large n and some new constant
$c_{1}> 0$
, we have
$[0, c_{1}n^{\alpha h/(h-2)}] \subset S^{(n)}_{H}$
.
Proof. Consider an empty graph G with vertex set
$V = V_{1} \sqcup V_{2}$
, where
$n_{1} = |V_{1}| = c'n^{\alpha /(h-2)}$
and
$n_{2} =|V_{2}| = n- |V_{1}|$
, and where
$c'> 0$
will be chosen later. Let
$G_{0} = G$
and let
$G_{i+1}$
be a graph obtained by adding an edge between vertices of
$V_{1}$
in
$G_{i}$
. Since H is connected,
$$ \begin{align*} k_{H}(G_{i+1}) - k_{H}(G_{i}) \le g_{H}^{(n_{1})} \le c_{H}n_{1}^{h-2} = c_{H}c^{\prime h-2}n^{\alpha}. \end{align*} $$
Therefore, we obtain an increasing sequence in
$S^{(n)}_{H}$
, starting with
$0$
and ending with
$k_{H}(G_{\binom {n_{1}}{2}})$
, such that the differences between consecutive terms are at most
$c_{H}c^{\prime h-2}n^{\alpha }$
. We modify
$G_{i}[V_{2}]$
to obtain the missing numbers between consecutive terms. By the hypothesis, we can modify
$G_{i}[V_{2}]$
to obtain
$G^{\prime }_{i}[V_{2}]$
containing any number k of copies of H, where
$k \in [0, cn_{2}^{\alpha }]$
. Hence, it suffices to find
$c'> 0$
such that
$c_{H}c^{\prime h-2}n^{\alpha } < cn_{2}^{\alpha }$
. We consider two cases depending on
$\alpha $
.
-
(1) If
$\alpha = h-2$
, then
$cn_{2}^{\alpha } = c( n-c'n )^{\alpha } = c(1-c')^{\alpha }n^{\alpha }$
. Therefore, it suffices to choose
$c'> 0$
such that
$c_{H}c^{\prime h-2} < c(1-c')$
. This gives
$g_{H}^{(n_{1})} < cn_{2}^{\alpha }$
. -
(2) If
$\alpha < h-2$
, then
$cn_{2}^{\alpha } = c( n - o(n) )^{\alpha } \sim cn^{\alpha }$
. If we choose
$c'> 0$
such that
${c' < ( c/c_{H} )^{1/(h-2)}}$
, then, for sufficiently large n, we again have
$g_{H}^{(n_{1})} < cn_{2}^{\alpha }$
.
Therefore, every number less than
$k_{H}(G_{\binom {n_{1}}{2}}) = k_{H}(K_{n_{1}})> c"n_{1}^{h} = c_{1}n^{\alpha h/(h-2)}$
is realisable.
If we have the same hypothesis, but with
$\alpha> h-2$
instead, from the next lemma we see that, for sufficiently large n, we can construct a graph on n vertices with k copies of H for any
$k \le (1-o(1))k_{H}(K_{n})$
.
Lemma 4.2. If
$[0, cn^{\alpha }] \subset S_{H}^{(n)}$
for sufficiently large n, where
$\alpha> h-2$
, then, for sufficiently large n,
$[0, (1-o(1))k_{H}(K_{n})] \subset S_{H}^{(n)}$
.
Proof. Proceeding as in Lemma 4.1, choose
$\beta \in ( (h-2)/\alpha , 1 )$
and let
$n_{2} = |V_{2}| = n^{\beta }$
and
$n_{1} = |V_{1}| = n - |V_{2}|$
. Note that
$g_{H}^{(n_{1})} = O(n^{h-2})$
. By the hypothesis, we can modify
$G[V_{2}]$
to obtain any number of copies of H up to
$cn_{2}^{\alpha }$
, where
$cn_{2}^{\alpha } = \omega (n^{h-2})$
. Therefore, every number in the interval
$[0, k_{H}(K_{n_{1}})]$
is realisable. However,
$n_{1} = (1-o(1))n$
, and hence
$k_{H}(K_{n_{1}}) = (1-o(1))k_{H}(K_n)$
.
Proof of Theorem 1.1.
We start by showing that, trivially,
$[ 0, \lfloor n/h \rfloor ] \subset S_{H}^{(n)}$
. To achieve that, note that, for any
$k \le \lfloor n/h \rfloor $
, we can simply construct a graph on n vertices consisting of k disjoint copies of H.
Let
$k_{\max }$
be the largest integer k such that
$({h}/{(h-2)})^{k} \le h$
(note that
$({h}/{(h-2)})^{k_{\max }} \in (h-2, h]$
). We claim that
$[0, c_{k}n^{(h/(h-2))^k} ] \subset S_{H}^{(n)}$
for every positive integer
$k \le k_{\max }$
and sufficiently large n. We prove the claim by induction on k. For
$k = 0$
, we already have
$[0, c_{0}n ] \subset S_{H}^{(n)}$
. Suppose that
$[ 0, c_{k} n^{(h/(h-2))^{k}} ] \in S_{H}^{(n)}$
and
$k < k_{\max }$
. Observe, first, that
$(h/(h-2))^{k} \le h-2$
, as otherwise
$(h/(h-2))^{k_{\max }}$
would be greater than h. Hence, we can apply Lemma 4.1 and conclude that
$[0, c_{k+1}n^{(h/(h-2))^{k+1}}] \in S_{H}^{(n)}$
for large enough n. Note that we apply Lemma 4.1 only finitely many times and hence n remains finite.
Therefore, for n large enough, we have
$[0, cn^{\alpha }] \subset S_{H}^{(n)}$
with
$\alpha = ({h}/{(h-2)})^{k_{\max }} \in (h-2, h]$
, and hence we can apply Lemma 4.2 and conclude that, for n sufficiently large,
$[0, (1-o(1))k_{H}(K_n)] \subset S_{H}^{(n)}$
.
We recall the major notation. For a graph
$G = (V, E)$
of order n, let
$f_{H}(G)$
be the number of subgraphs F of
$K(V)$
isomorphic to H such that
$E(F) \cap E \neq \emptyset $
, where
$K(V)$
denotes the complete graph on the vertex set V. Then the number of copies of H in G is equal to
$k_{H}(K_{n}) - f_{H}(\overline {G})$
. In the next lemma, we describe a formula for
$f_{H}$
.
Lemma 4.3. For any graphs H on h vertices and G on n vertices,
$$ \begin{align*} f_{H}(G) = c_{H}e(G)\binom{n-2}{h-2}-\sum_{k=2}^{e(H)}\sum_{\substack{e(F) = k \\ \delta(F)> 0} } (-1)^{k}c_{H}(F)k_{F}(G)\binom{n- |F|}{h - |F|}. \end{align*} $$
Proof. Let
$E(G) = \{ e_{1}, \ldots , e_{m} \}$
, where
$m = e(G)$
. Denote the set of subgraphs of the complete graph on
$V(G)$
isomorphic to H containing the edge
$e_{i}$
by
$A_i$
, that is,
$A_{i} = \{F \subset K(V): e_{i} \in E(F), F \cong H \}$
. Note that
$f_{H}(G) = | \bigcup _{i = 1}^{m} A_{i}|$
. Therefore, by the inclusion–exclusion principle,
$$ \begin{align*} f_{H}(G) = \sum_{k=1}^{m}\sum_{i_{1} < \cdots < i_{k}}(-1)^{k+1}|A_{i_{1}} \cap \cdots \cap A_{i_{k}} |. \end{align*} $$
For a graph F on at most h vertices, let
$c_{H}(F)$
be the number of copies of H in the complete graph
$K_{h}$
containing a fixed subgraph of the complete graph
$K_{h}$
, isomorphic to F. Let
$F = G[e_{i_{1}}, \ldots , e_{i_{k}}]$
be the graph induced by the edges
$e_{i_{1}}, \ldots , e_{i_{k}}$
. Observe that
$|A_{i_{1}} \cap \cdots \cap A_{i_{k}} | = c_{H}(F)\binom {n - |F|}{h-|F|}$
. Therefore,
$$ \begin{align*} f_{H}(G) &= \sum_{k=1}^{m}\sum_{i_{1} < \cdots < i_{k}}(-1)^{k+1}|A_{i_{1}} \cap \cdots \cap A_{i_{k}} | \\ &= \sum_{k=1}^{m}\sum_{\substack{F \subseteq H \\ e(F) = k \\ \delta(F)> 0}} (-1)^{k+1}k_{F}(G)c_{H}(F)\binom{n-|F|}{h-|F|} \\ &= c_{H}m\binom{n-2}{h-2}-\sum_{k=2}^{e(H)}\sum_{\substack{e(F) = k \\ \delta{F}> 0} } (-1)^{k}c_{H}(F)k_{F}(G)\binom{n- |F|}{h - |F|}.\\[-50pt] \end{align*} $$
The following easy lemma gives us an upper bound for
$k_{F}(G)$
.
Lemma 4.4. If F is a graph on f vertices with no isolated vertices, then, for every graph G on e edges, the number of copies of F in G is at most
$e^{f-1}$
.
Proof. We proceed by induction. The base case
$f = 2$
is trivial. Assume that
$f> 2$
and consider two cases. If F is a matching on
$f = 2l$
vertices, then the result follows easily: the number of copies of F in G is at most
$\binom {e}{l} \le e^{l} \le e^{2l-1} = e^{f-1}$
. In the other case, when F is not a matching, there exists a vertex
$v \in F$
such that
$F' = F - v$
has no isolated vertices. By the induction hypothesis, there are at most
$e^{f-2}$
copies of
$F'$
in G. Each copy of
$F'$
in G can be extended to at most e copies of F in G, since, by assumption, v must be adjacent to some vertex of
$F'$
. Therefore, there are at most
$e^{f-1}$
copies of F in G.
Lemma 4.5. Let G be a graph on n vertices with
$e = O(n^{1/2})$
edges. Then
$$ \begin{align*} f_{H}(G) = c_{H}e(G)\binom{n-2}{h-2} - c_{H}(P_{2})k_{P_{2}}(G)\binom{n-3}{h-3} + c_{H}(K_{3})k_{K_{3}}(G)\binom{n-3}{h-3} + o(n^{h-2}). \end{align*} $$
Proof. We consider the term
$c_{H}(F)k_{F}(G)\binom {n - |F|}{h-|F|}$
, where F is a graph on at least four vertices. From Lemma 4.4,
$k_{F}(G) \le e^{|F|-1}$
and so
$k_{F}(G)\binom {n-|F|}{h-|F|} \le e^{|F|-1}n^{h-|F|}$
. Hence, under the assumption that
$e = O(n^{1/2})$
,
$$ \begin{align*}k_{F}(G)\binom{n-|F|}{h-|F|} = O(n^{|F|/2-1/2}n^{h-|F|}) = O(n^{h-1/2-|F|/2}) = O(n^{h-5/2}) = o(n^{h-2}).\end{align*} $$
As there are only three graphs on fewer than four vertices with no isolated vertices, namely,
$K_{2}, K_{3}$
and
$P_{2}$
, and the number of terms in the summation in
$f(G)$
depends only on H, we can write
$$ \begin{align*}\hspace{-15pt} f_{H}(G) = c_{H}e(G)\binom{n-2}{h-2} - c_{H}(P_{2})k_{P_{2}}(G)\binom{n-3}{h-3} + c_{H}(K_{3})k_{K_{3}}(G)\binom{n-3}{h-3} + o(n^{h-2}).\\[-42pt] \end{align*} $$
The next lemma, which we use to prove that there are gaps in
$S_{H}^{(n)}$
, tells us that, for sufficiently large n, stars and matchings are asymptotically extremal examples of graphs for
$f_{H}(G)$
: that is, for a graph G on t edges,
$$ \begin{align*} a_{H}^{(n)}(t) - o(n^{h-2}) = f_{H}(S_{t}^{(n)}) - o(n^{h-2}) \le f_{H}(G) \le f_{H}(M_{t}^{(n)}) + o(n^{h-2}) = b_{H}^{(n)}(t) + o(n^{h-2}). \end{align*} $$
Lemma 4.6. Let G be a graph on n vertices with
$e = O(n^{1/2})$
edges. As
$n\to \infty $
:
-
(i)
$f_{H}(G) \ge a_{H}^{(n)}(e) - o(n^{h-2})= c_{H}e\binom {n-2}{h-2} - c_{H}(P_{2})\binom {e}{2}\binom {n-3}{h-3} + o(n^{h-2})$
; and -
(ii)
$f_{H}(G) \le b_{H}^{(n)}(e) + o(n^{h-2})= c_{H}e\binom {n-2}{h-2} + o(n^{h-2})$
.
Proof. This an immediate corollary of Lemma 4.5. Observe that
$k_{K_{3}}(S_{e}^{(n)}) = 0$
, as stars contain no triangles and
$k_{P_{2}}(S_{e}^{(n)}) = \binom {e}{2}$
. Therefore, by Lemma 4.5,
$$ \begin{align*} a_{H}^{(n)}(e) = c_{H}e\binom{n-2}{h-2} - c_{H}(P_{2})\binom{e}{2}\binom{n-3}{h-3} + o(n^{h-2}). \end{align*} $$
On the other hand, matchings contain no copies of
$K_{3}$
nor
$P_{2}$
, and hence, again, by Lemma 4.5,
$$ \begin{align*} b_{H}^{(n)}(e) = c_{H}e\binom{n-2}{h-2}+o(n^{h-2}). \end{align*} $$
For any graph G on e edges, we have
$k_{P_{2}}(G) \le \binom {e}{2}$
, so it follows from the above estimate on
$a_{H}^{(n)}(e)$
and from Lemma 4.5 that
$$ \begin{align*} f_{H}(G) \ge c_{H}e\binom{n-2}{h-2} - c_{H}(P_{2})\binom{e}{2}\binom{n-3}{h-3} + o(n^{h-2}) = a_{H}^{(n)}(e) - o(n^{h-2}). \end{align*} $$
On the other hand, it is easy to see that, for any graph G, we have
$c_{H}(P_{2})k_{P_{2}}(G) \ge c_{H}(K_{3})k_{K_{3}}(G)$
. So, by Lemma 4.5,
$$ \begin{align*} f_{H}(G) \le c_{H}e\binom{n-2}{h-2} + o(n^{h-2}) = b_{H}^{(n)}(e) + o(n^{h-2}).\\[-42pt] \end{align*} $$
Proof of Theorem 1.2.
Let
$t_{\max } = \max \{ t : b_{H}^{(n)}(t) < a_{H}^{(n)}(t+1) \}$
. First, we show that
$t_{\max } = \Theta (\sqrt {n})$
. Indeed,
$$ \begin{align*} a_{H}^{(n)}(t+1)-b_{H}^{(n)}(t) &= c_{H}\binom{n-2}{h-2}-c_{H}(P_{2})\binom{t+1}{2}\binom{n-3}{h-3} + o(n^{h-2}) \\ &= c_{1}n^{h-2} - c_{2}t^{2}n^{h-3} + o(n^{h-2}), \end{align*} $$
for some constants
$c_{1}, c_{2}> 0$
depending only on H. It follows that there is a constant C, depending only on H, such that, for all sufficiently large n, we have
$a_{H}^{(n)}(t+1)-b_{H}^{(n)}(t) \ge 0$
if
$t < C\sqrt {n}$
and
$a_{H}^{(n)}(t+1)-b_{H}^{(n)}(t) \le 0$
otherwise. From Lemma 4.6, for all sufficiently large n,
$$ \begin{align*} f_{H}(G) \in [a_{H}^{(n)}(e) - o(n^{h-2}), b_{H}^{(n)}(e) + o(n^{h-2})] \end{align*} $$
for a graph G with
$e \le t_{\max }$
edges. For a graph G with more than
$t_{\max }$
edges, let
$G'$
be a graph obtained from G by deleting some edges until there are exactly
$t_{\max }$
edges left. By monotonicity of f, we have
$f_H(G) \ge f_H(G') \ge a_{H}^{(n)}(t_{\max }) - o(n^{h-2})$
. Therefore, for any
$t < t_{\max }$
, the number of integers m in the interval
$( b_{H}^{(n)}(t), a_{H}^{(n)}(t+1) )$
such that there is a graph G on n vertices with
$f_{H}(G) = m$
is at most
$o(n^{h-2})$
. It follows that
$|(k_{H}(K_{n}) - a_{H}^{(n)}(t+1), k_{H}(K_{n}) - b_{H}^{(n)}(t)) \cap S_{H}^{(n)} | = o(n^{h-2})$
for every t.
Note that, when
$t < \tfrac 12t_{\max }$
, the gap between
$a_{H}^{(n)}(t+1)$
and
$b_{H}^{(n)}(t)$
is of order
$n^{h-2}$
. Hence, as n goes to infinity,
$$ \begin{align*} \frac{|( k_{H}(K_{n}) - a_{H}^{(n)}(t+1), k_{H}(K_{n}) - b_{H}^{(n)}(t)) \cap S_{H}^{(n)} |}{a_{H}^{(n)}(t+1)-b_{H}^{(n)}(t)} = o(1). \end{align*} $$
5 Open problems
We conclude our paper with some open problems that we feel would merit further study. Let
$\phi _{H}^{(n)} = \min \{ m \ge 0 : m \not \in S_{H}^{(n)} \}$
be the smallest nonmember of
$S_{H}^{(n)}$
. Therefore, we have proved that
$\phi _{K_{3}}^{(n)} = \binom {n}{3} - ( \sqrt {2} + o(1) )n^{3/2}$
and
$\phi _{P_{2}}^{(n)} = 3\binom {n}{3} - ( 4 + o(1) )n^{3/2}$
.
The ultimate goal is to determine
$S_{H}^{(n)}$
. In particular, we ask the following question.
Problem 5.1. What is the asymptotic behaviour of
$\binom {n}{r} - \phi _{K_{r}}^{(n)}$
?
We showed, in Lemma 2.3, that if
$e(G) = t \le t_{\max }$
, then
$f_{H}(G) \in [a_{H}^{(n)}(t), b_{H}^{(n)}(t)]$
. Simple constructions readily show that, in general, not every number in the interval
$[ a_{H}^{(n)}(t), b_{H}^{(n)}(t) ]$
is attained by
$f_{H}(G)$
. Therefore, we pose the following problem.
Problem 5.2. Determine the set
$[ a_{H}^{(n)}(t), b_{H}^{(n)}(t) ] - \{ f_{H}(G) : e(G) = t \}$
for
$t \le t_{\max }$
.
Acknowledgement
We thank Tomas Juškevičius for useful discussions.
