# A localized approach to generalized Turán problems

Rachel Kirsch
George Mason University
<EMAIL_ADDRESS>JD Nir
Toronto Metropolitan University
<EMAIL_ADDRESS>
(April 10, 2023)

###### Abstract

Generalized Turán problems ask for the maximum number of copies of a graph $H$
in an $n$-vertex, $F$-free graph, denoted by $\mathrm{ex}(n,H,F)$. We show how
to extend the new, localized approach of Bradač, Malec, and Tompkins to
generalized Turán problems. We weight the copies of $H$ (typically taking
$H=K_{t}$), instead of the edges, based on the size of the largest clique,
path, or star containing the vertices of the copy of $H$, and in each case
prove a tight upper bound on the sum of the weights. A consequence of our new
localized theorems is an asymptotic determination of
$\mathrm{ex}(n,H,K_{1,r})$ for every $H$ having at least one dominating vertex
and $\operatorname{\mathrm{mex}}(m,H,K_{1,r})$ for every $H$ having at least
two dominating vertices.

##  1 Introduction

Extremal graph theory is often considered the study of how easily measured
global graph parameters, such as the numbers of vertices and edges in a graph,
influence its local substructures [10]. An archetypical result due to Turán
describes which size cliques a graph is guaranteed to contain based on its
order and size:

######  Theorem (Turán [25]).

Let $n,r\geq 1$ be integers. If $G$ is a $K_{r+1}$-free graph on $n$ vertices
(that is, no subgraph of $G$ is isomorphic to the complete graph $K_{r+1}$),
then $G$ contains at most $\frac{n^{2}}{2}(1-\frac{1}{r})$ edges. This is
denoted

$\mathrm{ex}(n,K_{r+1})\leq\frac{n^{2}}{2}\Big{(}1-\frac{1}{r}\Big{)}.$

Furthermore, the $K_{r+1}$-free graph on $n$ vertices with the greatest number
of edges is the Turán graph, $T_{r}(n)$, in which the vertices of the graph
are partitioned into $r$ parts of sizes as close to equal as possible, and
vertices are adjacent if and only if they are in different parts.

Turán’s theorem has been generalized by many authors. In 2015, Alon and
Shikhelman [1], expanding on several sporadic results (e.g. [6, 17, 18]),
introduced the generalized Turán number $\mathrm{ex}(n,H,F)$, which denotes
the greatest number of subgraphs of an $F$-free graph on $n$ vertices that are
isomorphic to $H$. When maximizing the number of copies of $H\neq K_{2}$, it
is possible to fix the number of edges instead of the number of vertices.
Radcliffe and Uzzell [24] introduced the generalized edge Turán number,
$\operatorname{\mathrm{mex}}(m,H,F)$, which denotes the greatest number of
subgraphs that are isomorphic to $H$ in an $F$-free graph on $m$ edges.

The quantities $\mathrm{ex}(n,H,F)$ and $\operatorname{\mathrm{mex}}(m,H,F)$
have motivated many interesting results; see [8, 9, 14, 15, 16, 23] for an
(incomplete) sample. However, these problems often stretch the notion of
“easily measurable” properties on which extremal graph theory is based. Though
it is not known to be NP-complete, counting the number of subgraphs of $G$
that are isomorphic to $H$ is considered a challenging computation problem.
Therefore, practically, it may be difficult to determine whether a specific
$G$ contains a forbidden $F$ even when the exact value of $\mathrm{ex}(n,H,F)$
is known.

Recently, Bradač [7], based on a conjecture of Balogh and Lidický, gave a
fundamentally different generalization of Turán’s theorem:

######  Theorem (Bradač [7]).

Let $G$ be a graph on $n$ vertices. For each edge $e\in E(G)$, define its
weight $w(e)$ as

$w(e)=\frac{k}{2(k-1)}$

where $k$ is the size of the largest clique in $G$ containing $e$. Then

$\sum_{e\in E(G)}w(e)\leq n^{2}/4.$

This theorem has since been applied to Ramsey-Turán problems in [3, 4].

Bradač’s result generalizes Turán’s theorem in the following sense: if it is
known that $G$ is $K_{r+1}$-free, then, noting $w(e)$ is decreasing in $k$, we
see $w(e)\geq r/(2(r-1))$ for every edge $e$. Thus

$|E(G)|\cdot\frac{r}{(2(r-1))}\leq\sum_{e\in
E(G)}w(e)\leq\frac{n^{2}}{4}\implies|E(G)|\leq\frac{n^{2}}{2}\Big{(}1-\frac{1}{r}\Big{)}.$

The novelty of Bradač’s result is in the local nature of the weight function.
Rather than counting the total number of edges in the entire graph, a global
property, the weight we assign to each edge depends only on the neighborhoods
of the vertices of that edge which may be computed more efficiently.

Inspired by Bradač’s result, Malec and Tompkins [22] investigated other
results which could be “localized” in a similar fashion. In addition to giving
a new proof of Bradač’s result, they proved a local version of another
celebrated extremal graph theory result of Erdős and Gallai, as well as the
LYMB inequality (a generalization of Sperner’s theorem on boolean lattices), a
generalization of the Erdős-Ko-Rado theorem, and a theorem of Erdős and
Szekeres on sequences.

Both Turán’s theorem and the theorem of Erdős and Gallai considered by Malec
and Tompkins tell us something about the graph based on the number of edges it
contains. Keeping in mind that an edge is a clique containing two vertices,
natural generalizations of both results to cliques of larger size have been
investigated. In this article, we show that these results, too, admit
localized generalizations. In fact, we prove several local results by
weighting the cliques or other subgraphs of $G$ of a given size based on the
maximum size of various substructures that contain them. In some cases these
“generalizations” actually establish new extremal results.

Our results follow a general framework. Each theorem concerns a target
subgraph $H$, which in many cases is a clique of some fixed size, and a family
$\mathcal{F}=\\{F_{1},F_{2},\ldots\\}$ of graphs in which $F_{i}\subseteq
F_{i+1}$. We first establish a size function which, given a copy of $H$ in
$G$, returns the largest $F_{i}$ such that some subgraph of $G$ isomorphic to
$F_{i}$ contains $H$ in some meaningful way. Then we define a weight function
which depends only on the size function of $H$ and prove a bound on the sum of
the weights of every copy of $H$ in $G$. In each case we show that the weight
function is a decreasing function of the size function, so a global upper
bound on the size function implies a lower bound on the sum of the weights,
and we recover a “non-localized” theorem.

The rest of this paper is arranged as follows. We begin with some notational
conventions and preliminary results in Section 2. Then in Section 3, we weight
$t$-cliques in $G$ by the size of the largest clique containing them to
generalize Zykov’s theorem, itself a direct extension of Turán’s theorem. We
weight $t$-cliques by the longest path containing their vertices in Section 4,
considering graphs of fixed order in Section 4.1 and graphs of fixed size in
Section 4.2. We weight a broad class of graphs, including cliques, by the size
of the largest star containing their vertices in Section 5.1, in which we
prove a family of novel generalized Turán and edge Turán results. We also give
a hypergraph version of one of these localized results in Section 5.2. We
conclude with some open questions in Section 6.

##  2 Preliminaries

###  2.1 Notation

In addition to standard graph theoretic notation (see [5], for example), we
establish the following conventions. We define the path graph $P_{n}$ to have
$n$ vertices and $n-1$ edges and the star graph $S_{r}$ to have $r$ leaves
(and thus $r+1$ total vertices). Given graphs $G$ and $H$, we let
$\mathcal{N}(H,G)$ denote the number of subgraphs of $G$ that are isomorphic
to $H$. If $\mathcal{N}(H,G)=0$, we say $G$ is $H$-free. As mentioned in the
introduction, if $H$ and $F$ are graphs, then

$\mathrm{ex}(n,H,F)=\max\\{\mathcal{N}(H,G):|V(G)|=n\text{ and }\text{$G$ is
$F$-free}\\}$

and

$\operatorname{\mathrm{mex}}(m,H,F)=\max\\{\mathcal{N}(H,G):|E(G)|=m\text{ and
}\text{$G$ is $F$-free}\\}.$

We also have need to refer to the copies of $H$ in $G$. When we do so for
cliques, we refer to the sets of vertices that span a complete subgraph and
write

$\mathcal{K}^{t}(G)=\\{S\subseteq V(G):G[S]\cong K_{t}\\}.$

For a more general graph $H$, we write $\mathcal{H}(G)$ to refer to the set of
(not necessarily induced) subgraphs of $G$ that are isomorphic to $H$.

The size function and weight function(s) in each section are denoted by the
notation shown below.

| Cliques | Paths | Stars (graphs) | Stars (hypergraphs)
---|---|---|---|---
Section | 3 | 4 | 5.1 | 5.2
Size function | $\alpha_{G}$ | $\beta_{G}$ | $\theta_{G}$ | $x$
Weight function(s) | $w_{G}$ |  $p_{G}$, $p^{\prime}_{G}$ | $s_{G}^{u}$ | $s$

###  2.2 Generalized binomial coefficients

We use generalized binomial coefficients when working with paths in Section 4
and hypergraphs in Section 5. For a real number $x\geq k-1$ and a natural
number $k$, the _generalized binomial coefficient_ $\binom{x}{k}$ is defined
as $(x)(x-1)\cdots(x-k+1)/k!$. When $x<k-1$, we set $\binom{x}{k}=0$. The
function $\binom{x}{k}$ is weakly increasing for all real numbers $x$ and
strictly increasing on $x\geq k-1$.

######  Observation 2.1.

For all $x\in\mathbb{R}$ and $n\in\mathbb{N}$, we have

$2^{n}\binom{x}{n}\leq\binom{2x}{n},$

with strict inequality when $2x+1>n\geq 2$.

###### Proof.

The right side is always non-negative and is positive for $2x>n-1$. When
$x\leq n-1$, the left side is zero. When $x>n-1$, the inequality is equivalent
to

$(2x)(2x-2)\cdots(2x-2n+2)\leq(2x)(2x-1)\cdots(2x-n+1),$

so is strict when $n\geq 2$. ∎

In Section 4 we also use the following observation and theorem.

######  Observation 2.2.

Let $G$ be a graph having at least one edge. Write $|E(G)|$ in the form
$\binom{x}{2}$, where $x\geq 2$ is real. Then $|V(G)|\geq x$.

###### Proof.

If $|V(G)|<x$ then $|V(G)|\leq\lceil x\rceil-1$, so $|E(G)|\leq\binom{\lceil
x\rceil-1}{2}<\binom{x}{2}$. Here we used that the generalized binomial
coefficient $\binom{y}{2}$ is strictly increasing for all $y\geq 1$. ∎

######  Theorem 2.3 (Lovász [20]).

Let $t\geq 2$. Let $G$ be a graph. Write the number of edges of $G$ in the
form $\binom{x}{2}$, where $x\geq 1$ is real. Then
$\mathcal{N}(K_{t},G)\leq\binom{x}{t}$.

We also use generalized binomial coefficients in Section 5.2, where we
introduce hypergraph definitions and notation before stating 5.7, a bound on
the number of $t$-cliques in a $q$-uniform hypergraph based on the number of
edges, which is a version of Lovász’s approximate form of the Kruskal-Katona
theorem. 2.3 is the special case of 5.7 corresponding to graphs.

##  3 Weighting by Maximum Clique Size

In this section we prove the following theorem which extends the localized
version of Turán’s theorem in [22] by assigning weights to cliques of any
size, rather than just edges. Then we show that it simultaneously extends a
different extension of Turán’s theorem due to Zykov.

######  Theorem 3.1.

Let $t\geq 2$. For each $T\in\mathcal{K}^{t}(G)$, define

$\alpha_{G}(T)=\max\\{k:T\subseteq V(S)\textnormal{ for some }S\subseteq G\
\text{s.t.}\,S\cong K_{k}\\}\quad\text{and}\quad
w_{G}(T)=\frac{\alpha_{G}(T)^{t}}{\binom{\alpha_{G}(T)}{t}}.$

Then $w_{G}(T)$ is well-defined and decreasing in $\alpha_{G}(T)$, and

$w(G)=\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)\leq n^{t},$

with equality if and only if $G$ is a balanced multipartite graph with at
least $t$ parts.

Note that by setting $t=2$, we recover the result which is Theorem 1 of both
[7] and [22].

$\sum_{T\in\mathcal{K}^{2}(G)}\frac{\alpha_{G}(e)^{2}}{\binom{\alpha_{G}(e)}{2}}=\sum_{e\in
E(G)}\frac{2\alpha_{G}(e)}{\alpha_{G}(e)-1}\leq n^{2}\implies\sum_{e\in
E(G)}\frac{\alpha_{G}(e)}{\alpha_{G}(e)-1}\leq\frac{n^{2}}{2}.$

###### Proof.

First, $\alpha_{G}(T)\geq t$ because $G[T]\cong K_{t}$, and therefore
$w_{G}(T)$ is well-defined. We observe $w_{G}(T)$ is decreasing in
$\alpha_{G}(T)$ as we can write

$w_{G}(T)=t!\cdot\frac{\alpha_{G}(T)^{t}}{\prod_{i=0}^{t-1}(\alpha_{G}(T)-i)}=t!\cdot\prod_{i=1}^{t-1}\Big{(}1+\frac{i}{\alpha_{G}(T)-i}\Big{)},$

which is a non-empty product of functions decreasing in $\alpha_{G}(T)$.

Let $G$ be a graph on $n\geq 3$ vertices. Note that if $G$ contains an edge
$e$ that is not contained in any $t$-clique, then $e$ also is not contained in
any larger clique, so $\mathcal{K}^{t}(G-e)=\mathcal{K}^{t}(G)$,
$w_{G-e}(T)=w_{G}(T)$ for every $T\in\mathcal{K}^{t}(G)$, and $w(G)=w(G-e)$.
Therefore we may assume that every edge in $G$ is contained in a $t$-clique.
First assume there is $r\geq t$ such that $G$ is complete $r$-partite with
(non-empty) parts $A_{1},\ldots,A_{r}$. Then for each $T\in\mathcal{K}^{t}(G)$
we have $\alpha_{G}(T)=r$ and $w_{G}(T)=r^{t}/\binom{r}{t}$. This gives

$\displaystyle w(G)$
$\displaystyle=\frac{r^{t}}{\binom{r}{t}}\mathcal{N}(K_{t},G)$
$\displaystyle=\frac{r^{t}}{\binom{r}{t}}\sum_{S\in\binom{[r]}{t}}\prod_{s\in
S}|A_{s}|$

To bound this sum, we relax the condition that the parts have integral sizes.
By symmetry, the real-valued polynomial function

$f(x_{1},\ldots,x_{r})=\sum_{S\in\binom{[r]}{t}}\prod_{i\in S}x_{i}$

has a unique maximum when each $x_{i}=n/r$, in which case each of the
$\binom{r}{t}$ terms is $(n/r)^{t}$, and thus

$w(G)\leq\frac{r^{t}}{\binom{r}{t}}\cdot\binom{r}{t}\cdot\left(\frac{n}{r}\right)^{t}=n^{t}$

with equality if and only if $|A_{i}|=n/r$.

Thus we may assume $G$ is not complete multipartite. We use a technique
introduced by Zykov [27] sometimes called Zykov symmetrization. Suppose there
are $x,y,z\in V(G)$ such that $x\sim z$ but $x\not\sim y\not\sim z$. We show
that as long as such vertices exist, we can find $G^{\prime}$ on $n$ vertices
such that $w(G^{\prime})>w(G)$. If no such vertices exist, then $x\not\sim y$
and $y\not\sim z$ implies $x\not\sim z$, which is to say nonadjacent vertices
can be partitioned into equivalence classes and therefore $G$ is complete
multipartite. Thus producing such a $G^{\prime}$ reduces this case to the
complete multipartite case, and furthermore proves any graph that meets the
bound in the theorem must be complete multipartite.

For convenience, for $v\in V(G)$, define

$w_{G}(v)=\sum_{\begin{subarray}{c}T\in\mathcal{K}^{t}(G)\\\ \text{s.t.}\ v\in
T\end{subarray}}w_{G}(T).$

Assume without loss of generality that $w_{G}(x)\geq w_{G}(z)$ and consider
two cases.

######  Case 3.1.1.

$w_{G}(x)>w_{G}(y)$.

Introduce a new vertex $x^{\prime}$, add edges so that $N(x^{\prime})=N(x)$,
and let $G^{\prime}=G-y+x^{\prime}$. Consider a clique $K^{\prime}$ (of any
size) that is present in $G^{\prime}$ but not in $G$. Such a clique must
contain $x^{\prime}$ and so must be contained in
$N_{G^{\prime}}[x^{\prime}]\cong N_{G}[x]$. Therefore any
$T\in\mathcal{K}^{t}(G)$ contained in $K^{\prime}$ is also contained in some
clique $K\subseteq V(G)$ of the same size. Thus every
$T\in\mathcal{K}^{t}(G)\cap\mathcal{K}^{t}(G^{\prime})$ has
$\alpha_{G}(T)\geq\alpha_{G^{\prime}}(T)$. As $w_{G}(T)$ is decreasing in
$\alpha_{G}(T)$, we have $w_{G}(T)\leq w_{G^{\prime}}(T)$. Then

$\displaystyle\sum_{T\in\mathcal{K}^{t}(G^{\prime})}w_{G^{\prime}}(T)$
$\displaystyle=\sum_{T\in\mathcal{K}^{t}(G^{\prime})\setminus\mathcal{K}^{t}(G)}w_{G^{\prime}}(T)+\sum_{T\in\mathcal{K}^{t}(G^{\prime})\cap\mathcal{K}^{t}(G)}w_{G^{\prime}}(T)$
$\displaystyle\geq\sum_{T\in\mathcal{K}^{t}(G^{\prime})\setminus\mathcal{K}^{t}(G)}w_{G^{\prime}}(T)+\sum_{T\in\mathcal{K}^{t}(G-y)}w_{G}(T)$
$\displaystyle=w_{G^{\prime}}(x^{\prime})+\Big{(}\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)-w_{G}(y)\Big{)}$
$\displaystyle=w_{G}(x)+\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)-w_{G}(y)$
$\displaystyle>\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T).$

######  Case 3.1.2.

$w_{G}(x)\leq w_{G}(y)$.

In this case we introduce two new vertices, $y^{\prime}$ and
$y^{\prime\prime}$, add edges such that
$N(y^{\prime\prime})=N(y^{\prime})=N(y)$, and define
$G^{\prime\prime}=G-x-z+y^{\prime}+y^{\prime\prime}$. As before, every clique
$K^{\prime}$ that is in $G^{\prime\prime}$ but not in $G$ must contain
$y^{\prime}$ or $y^{\prime\prime}$ (but not both as $y^{\prime}\not\sim
y^{\prime\prime}$). Thus once again $K^{\prime}$ must be contained in
$N_{G^{\prime\prime}}[y^{\prime}]\cong N_{G}[y]$ or
$N_{G^{\prime\prime}}[y^{\prime\prime}]\cong N_{G}[y]$, so every
$T\in\mathcal{K}^{t}(G)\cap\mathcal{K}^{t}(G^{\prime\prime})$ has
$\alpha_{G}(T)\geq\alpha_{G^{\prime\prime}}(T)$ and $w_{G}(T)\leq
w_{G^{\prime\prime}}(T)$. Therefore

$\displaystyle\sum_{T\in\mathcal{K}^{t}(G^{\prime\prime})}w_{G^{\prime\prime}}(T)$
$\displaystyle=\sum_{T\in\mathcal{K}^{t}(G^{\prime\prime})\setminus\mathcal{K}^{t}(G)}w_{G^{\prime\prime}}(T)+\sum_{T\in\mathcal{K}^{t}(G^{\prime\prime})\cap\mathcal{K}^{t}(G)}w_{G^{\prime\prime}}(T)$
$\displaystyle\geq\sum_{T\in\mathcal{K}^{t}(G^{\prime\prime})\setminus\mathcal{K}^{t}(G)}w_{G^{\prime\prime}}(T)+\sum_{T\in\mathcal{K}^{t}(G-x-z)}w_{G}(T)$
$\displaystyle=w_{G^{\prime\prime}}(y^{\prime})+w_{G^{\prime\prime}}(y^{\prime\prime})+\Big{(}\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)-w_{G}(x)-w_{G}(z)+\sum_{\begin{subarray}{c}T\in\mathcal{K}^{t}(G)\\\
\text{s.t.}\ x,z\in T\end{subarray}}w_{G}(T)\Big{)}$
$\displaystyle=2w_{G}(y)+\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)-w_{G}(x)-w_{G}(z)+\sum_{\begin{subarray}{c}T\in\mathcal{K}^{t}(G)\\\
\text{s.t.}\ x,z\in T\end{subarray}}w_{G}(T)$
$\displaystyle\geq\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)+\sum_{\begin{subarray}{c}T\in\mathcal{K}^{t}(G)\\\
\text{s.t.}\ x,z\in T\end{subarray}}w_{G}(T)$
$\displaystyle>\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T),$

where the last step holds because $x\sim z$, and our initial assumption
guarantees every edge is contained in a $t$-clique. ∎

One can also view Theorem 3.1 as a generalization of a theorem of Zykov [27]
(and independently Erdős [11]). In what is now considered the first
generalized Turán result, Zykov proved that, among $K_{r+1}$-free graphs, the
Turán graph $T_{r}(n)$ maximizes not only the number of edges but the number
of cliques of any size.

######  Theorem 3.2 (Zykov [27]).

Let $G$ be a $K_{r+1}$-free graph on $n$ vertices. Then for any $t\geq 1$,

$\mathcal{N}(K_{t},G)\leq\binom{r}{t}\left(\frac{n}{r}\right)^{t}.$

Note that Zykov actually proved the stronger result that
$\mathrm{ex}(n,K_{t},K_{r+1})=\mathcal{N}(K_{t},T_{r}(n))$, though these
results agree when $r\mathrel{\bigm{|}}n$.

We can prove Theorem 3.2 as a consequence of Theorem 3.1:

###### Proof of 3.2.

Let $G$ be a an $n$-vertex, $K_{r+1}$-free graph. Then for each
$T\in\mathcal{K}^{t}(G)$ we have $\alpha_{G}(T)\leq r$ and, as $w_{G}(T)$ is
decreasing in $\alpha_{G}(T)$, $w_{G}(T)\geq r^{t}/\binom{r}{t}$. Thus by
Theorem 3.1,

$\mathcal{N}(K_{t},G)\cdot\frac{r^{t}}{\binom{r}{t}}=\sum_{T\in\mathcal{K}^{t}(G)}\frac{r^{t}}{\binom{r}{t}}\leq\sum_{T\in\mathcal{K}^{t}(G)}w_{G}(T)\leq
n^{t}$

and so

$\mathcal{N}(K_{t},G)\leq\frac{\binom{r}{t}}{r^{t}}\cdot
n^{t}=\binom{r}{t}\left(\frac{n}{r}\right)^{t}.\qed$

##  4 Weighting by Maximum Path Length

In 1959, Erdős and Gallai [12] proved that every graph with $n$ vertices and
$m$ edges contains a path of length at least $2m/n$, and as a consequence
$\mathrm{ex}(n,K_{2},P_{r+1})\leq\frac{(r-1)n}{2}$, which, when
$r\mathrel{\bigm{|}}n$, is achieved by a disjoint union of copies of $K_{r}$.
Luo [21] determined $\mathrm{ex}(n,K_{t},P_{r+1})$ asymptotically, and
Chakraborti and Chen [8] then determined
$\operatorname{\mathrm{mex}}(m,K_{t},P_{r+1})$. Malec and Tompkins [22] gave a
local version of the Erdős-Gallai result. To extend their result to the
$t$-clique versions, considering both graphs of fixed order and graphs of
fixed size, we define a more general size function for paths.

######  Definition 4.1.

Let $G$ be a graph on $n$ vertices and $t\geq 2$. For each
$T\in\mathcal{K}^{t}(G)$, define

$\beta_{G}(T)=\max\\{k:T\subseteq V(S)\textnormal{ for some }S\subseteq G\
\text{s.t.}\,S\cong P_{k+1}\\}.$

###  4.1 Paths in graphs of fixed order

In this section we extend a result of Malec and Tompkins [22, Theorem 2] to
cliques, which we will demonstrate also generalizes a result of Luo [21].

######  Theorem 4.2.

Let $G$ be a graph on $n$ vertices and $t\geq 2$. Define

$p_{G}(T)=\frac{1}{\binom{\beta_{G}(T)}{t-1}}.$

Then $p_{G}(T)$ is well-defined and decreasing in $\beta_{G}(T)$, and

$\sum_{T\in\mathcal{K}^{t}(G)}p_{G}(T)\leq\frac{n}{t},$

with equality if and only if $G$ is a disjoint union of complete graphs of
order at least $t$.

We note that setting $t=2$ does not quite recover [22, Theorem 2] as our
weight function is not equivalent at $t=2$. Malec and Tompkins define
$\beta_{MT}(e)$ to be the longest path containing the edge $e$ as a subgraph.
This definition does not extend to larger cliques as paths do not contain them
as subgraphs. Instead, we merely require that all vertices of the clique
appear in the path. Thus when $t=2$, unlike for Malec and Tompkins, the
vertices of our edge may occur in the path without the edge being part of the
path.

###### Proof.

First, we note any ordering of the vertices in any $T\in\mathcal{K}^{t}(G)$ is
a path of length $t-1$, so $\beta_{G}(T)\geq t-1$ and
$\binom{\beta_{G}(T)}{t-1}>0$. Therefore $p_{G}(T)$ is well-defined and
decreasing in $\beta_{G}(T)$.

We proceed by induction on $n$. When $1\leq n\leq t-1$ we have

$\sum_{T\in\mathcal{K}^{t}(G)}p_{G}(T)=0<\frac{n}{t}.$

If $G$ is not connected, let $C_{1},\ldots,C_{q}$ be the components of $G$.
Applying the inductive hypothesis to each component, we have

$\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}p_{G}(T)$
$\displaystyle=\sum_{i=1}^{q}\sum_{T\in\mathcal{K}^{t}(C_{i})}p_{G}(T)$
$\displaystyle=\sum_{i=1}^{q}\sum_{T\in\mathcal{K}^{t}(C_{i})}p_{C_{i}}(T)$
$\displaystyle\leq\sum_{i=1}^{q}\frac{|V(C_{i})|}{t}\quad\text{by induction}$
$\displaystyle=\frac{n}{t}.$

Therefore we may assume $G$ is connected and $n\geq t$. Let $r$ be the length
of a longest path $P\cong P_{r+1}$ in $G$.

######  Case 4.2.1.

There exists a cycle $C$ containing the vertices of $P$.

Suppose for the sake of contradiction that there is a vertex $u$ that is not
on the cycle $C$. Since $G$ is connected, there is a path from $u$ to $C$ and
then around $C$, which is longer than $P$, contradicting that $P$ is a longest
path. Therefore every vertex of $G$ is on $C$. Each $T\in\mathcal{K}^{t}(G)$
is contained in a path of length $n-1$ and has $p_{G}(T)=1/\binom{n-1}{t-1}$.

Hence,

$\sum_{T\in\mathcal{K}^{t}(G)}p_{G}(T)=\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{n-1}{t-1}}=\frac{\mathcal{N}(K_{t},G)}{\binom{n-1}{t-1}}\leq\frac{\binom{n}{t}}{\binom{n-1}{t-1}}=\frac{n}{t},$

and equality implies $G\cong K_{n}$, with $n\geq t$.

######  Case 4.2.2.

There does not exist a cycle $C$ containing the vertices of $P$.

Let $v$ and $w$ be the endpoints of $P$. Then $\\{v,w\\}\notin E(G)$. Label
the vertices of $P$ in order as $(v=u_{1},u_{2},\ldots,u_{r+1}=w)$. Let
$V=\\{i:v\sim u_{i}\\}$ and $W=\\{i:w\sim u_{i-1}\\}$. If $i\in V\cap W$ then
$(u_{i},u_{1},u_{2},\ldots,u_{i-1},u_{r+1},u_{r},\ldots,u_{i})$ is a cycle
containing the vertices of $P$, so $V\cap W=\emptyset$. Since
$V,W\subseteq\\{2,\ldots,r+1\\}$, we have $d(v)+d(w)=|V|+|W|=|V\cup W|\leq r$.
Assume, without loss of generality, that $d(v)\leq r/2$.

Let $R(v)$ be the set of $t$-cliques of $G$ that contain $v$. Then
$|R(v)|\leq\binom{d(v)}{t-1}$. The fact that $P$ is a longest path implies
both that $\beta_{G}(T)\leq r$ and that every $t$-clique $T$ in $R(v)$ is
contained in $V(P)$ (so $\beta_{G}(T)\geq r$), and therefore
$p_{G}(T)=1/\binom{r}{t-1}$ for every $T\in R(v)$. For any
$T\in\mathcal{K}^{t}(G-v)$, we see $\beta_{G-v}(T)\leq\beta_{G}(T)$ and
therefore, as $p_{G}$ is decreasing in $\beta_{G}(T)$, $p_{G-v}(T)\geq
p_{G}(T)$.

Applying the inductive hypothesis to $G-v$, we get

$\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}p_{G}(T)$
$\displaystyle=\sum_{T\in\mathcal{K}^{t}(G-v)}p_{G}(T)+\sum_{T\in
R(v)}p_{G}(T)$
$\displaystyle\leq\sum_{T\in\mathcal{K}^{t}(G-v)}p_{G-v}(T)+\sum_{T\in
R(v)}p_{G}(T)$ $\displaystyle\leq\frac{n-1}{t}+\frac{|R(v)|}{\binom{r}{t-1}}$
$\displaystyle\leq\frac{n-1}{t}+\frac{\binom{d(v)}{t-1}}{\binom{r}{t-1}}$
$\displaystyle\leq\frac{n-1}{t}+\frac{\binom{r/2}{t-1}}{\binom{r}{t-1}}$
$\displaystyle\leq\frac{n-1}{t}+\frac{(1/2)^{t-1}\binom{r}{t-1}}{\binom{r}{t-1}}$
by 2.1 $\displaystyle=\frac{n-1}{t}+\frac{1}{2^{t-1}}$
$\displaystyle\leq\frac{n-1}{t}+\frac{1}{t}$ $\displaystyle=\frac{n}{t}$

as $2^{t-1}\geq t$ when $t\geq 2$. When $t\geq 3$, we see $2^{t-1}>t$ and thus
if equality holds, no component is in Case 4.2.2, so every component is in
Case 4.2.1, and every component is a clique.

When $t=2$, the claim that equality holds only for cliques follows from [22,
Theorem 2]. Though, as noted, our definition of $\beta_{G}(T)$ does not quite
match their $\beta_{MT}(e)$, we have $\beta_{MT}(e)\leq\beta_{G}(e)$ as any
path containing an edge also contains the vertices of that edge. Because

$p_{G}(T)=\frac{1}{\binom{\beta_{G}(T)}{2-1}}=\frac{1}{\beta_{G}(T)}$

is decreasing and matches Malec and Tompkins’ weight, we see

$\sum_{T\in\mathcal{K}^{2}(G)}p_{G}(T)=\sum_{e\in
E(G)}\frac{1}{\beta_{G}(e)}\leq\sum_{e\in E(G)}\frac{1}{\beta_{MT}(e)}.$

Therefore if equality holds in our result, it also holds in Malec and
Tompkins’ result, and by Theorem 2 in [22], $G$ is a disjoint union of
complete graphs. ∎

In 2018, Luo [21] extended Erdős and Gallai’s theorem by showing disjoint
unions of cliques maximize the number of cliques of any size.

######  Theorem 4.3 (Luo [21]).

Let $G$ be a $P_{r+1}$-free graph on $n$ vertices. Then for any $t\leq r$,

$\mathcal{N}(K_{t},G)\leq\frac{n}{r}\binom{r}{t}.$

Furthermore, equality holds if and only if $r\mathrel{\bigm{|}}n$ and $G$ is a
disjoint union of copies of $K_{r}$.

We note that Theorem 4.2 generalizes Theorem 4.3:

###### Proof.

Let $G$ be a $P_{r+1}$-free graph on $n$ vertices. In such a graph $G$, every
$T\in\mathcal{K}^{t}(G)$ has $\beta_{G}(T)\leq r-1$, so
$p_{G}(T)\geq\frac{1}{\binom{r-1}{t-1}}$. By Theorem 4.2,

$\frac{\mathcal{N}(K_{t},G)}{\binom{r-1}{t-1}}=\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{r-1}{t-1}}\leq\sum_{T\in\mathcal{K}^{t}(G)}p_{G}(T)\leq\frac{n}{t},$

so

$\mathcal{N}(K_{t},G)\leq\frac{n}{t}\binom{r-1}{t-1}=\frac{n}{r}\binom{r}{t}.$

By 4.2, equality implies that every component is a $P_{r+1}$-free clique, and
that every $t$-clique is contained in a $P_{r}$, so $G$ is a disjoint union of
copies of $K_{r}$. ∎

###  4.2 Paths in graphs of fixed size

Chakraborti and Chen [8] asked and answered the edge variant of this question
by determining $\operatorname{\mathrm{mex}}(m,K_{t},P_{r+1})$ exactly for all
values of the parameters $m$, $t$, and $r$. We prove a localized form of their
result, then show that it implies an asymptotic determination of
$\operatorname{\mathrm{mex}}(m,K_{t},P_{r+1})$.

######  Theorem 4.4.

Let $t\geq 3$. Let $G$ be a graph having $m$ edges. For each
$T\in\mathcal{K}^{t}(G)$, define

$p^{\prime}_{G}(T)=\frac{1}{\binom{\beta_{G}(T)-1}{t-2}}.$

Then $p^{\prime}_{G}(T)$ is well-defined and decreasing in $\beta_{G}(T)$, and

$\sum_{T\in\mathcal{K}^{t}(G)}p^{\prime}_{G}(T)\leq\frac{m}{\binom{t}{2}},$

with equality if and only if $G$ is a disjoint union of complete graphs of
order at least $t$ and any number of isolated vertices.

###### Proof.

As before, any ordering of the vertices in any $T\in\mathcal{K}^{t}(G)$ is a
path of length $t-1$, so $\beta_{G}(T)\geq t-1$ and
$\binom{\beta_{G}(T)-1}{t-2}>0$. Therefore $p^{\prime}_{G}(T)$ is well-defined
and decreasing in $\beta_{G}(T)$.

We proceed by induction on $m$. When $1\leq m\leq\binom{t}{2}-1$ we have

$\sum_{T\in\mathcal{K}^{t}(G)}p^{\prime}_{G}(T)=0<\frac{m}{\binom{t}{2}}.$

If $G$ is not connected, let $C_{1},\ldots,C_{q}$ be the components of $G$.
Applying the inductive hypothesis to each component, we have

$\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}p^{\prime}_{G}(T)$
$\displaystyle=\sum_{i=1}^{q}\sum_{T\in\mathcal{K}^{t}(C_{i})}p^{\prime}_{G}(T)$
$\displaystyle=\sum_{i=1}^{q}\sum_{T\in\mathcal{K}^{t}(C_{i})}p^{\prime}_{C_{i}}(T)$
$\displaystyle\leq\sum_{i=1}^{q}\frac{|E(C_{i})|}{\binom{t}{2}}\quad\text{by
induction}$ $\displaystyle=\frac{m}{\binom{t}{2}}.$

Therefore we may assume $G$ is connected and $m\geq\binom{t}{2}$. Let $r$ be
the length of a longest path $P\cong P_{r+1}$ in $G$.

######  Case 4.4.1.

There exists a cycle $C$ containing the vertices of $P$.

Suppose for the sake of contradiction that there is a vertex $u$ that is not
on the cycle $C$. Since $G$ is connected, there is a path from $u$ to $C$ and
then around $C$, which is longer than $P$, contradicting that $P$ is a longest
path. Therefore every vertex of $G$ is on $C$. Each $T\in\mathcal{K}^{t}(G)$
is contained in a path of length $|V(G)|-1$, and has
$p^{\prime}_{G}(T)=1/\binom{|V(G)|-2}{t-2}$. Let $x\geq t$ be a real number
satisfying $m=\binom{x}{2}$. Then we have $|V(G)|\geq x$ by 2.2 and, by 2.3,
$\mathcal{N}(K_{t},G)\leq\binom{x}{t}$. Hence,

$\sum_{T\in\mathcal{K}^{t}(G)}p^{\prime}_{G}(T)=\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{|V(G)|-2}{t-2}}=\frac{\mathcal{N}(K_{t},G)}{\binom{|V(G)|-2}{t-2}}\leq\frac{\binom{x}{t}}{\binom{x-2}{t-2}}=\frac{\binom{x}{2}}{\binom{t}{2}}=\frac{m}{\binom{t}{2}},$

and equality implies $\binom{|V(G)|-2}{t-2}=\binom{x-2}{t-2}$ with
$x-2\geq(t-2)-1$, so $x=|V(G)|$. Then
$\mathcal{N}(K_{t},G)=\binom{|V(G)|}{t}$, so $G\cong K_{x}$ (and $x\geq t$).

######  Case 4.4.2.

There does not exist a cycle $C$ containing the vertices of $P$.

Let $v$ and $w$ be the endpoints of $P$. Then $\\{v,w\\}\notin E(G)$. Label
the vertices of $P$ in order as $(v=u_{1},u_{2},\ldots,u_{r+1}=w)$. Let
$V=\\{i:v\sim u_{i}\\}$ and $W=\\{i:w\sim u_{i-1}\\}$. If $i\in V\cap W$ then
$(u_{i},u_{1},u_{2},\ldots,u_{i-1},u_{r+1},u_{r},\ldots,u_{i})$ is a cycle
containing the vertices of $P$. Because $V,W\subseteq\\{2,\ldots,r+1\\}$, we
have $d(v)+d(w)=|V|+|W|=|V\cup W|\leq r$. Assume, without loss of generality,
that $d(v)\leq r/2$.

Let $R(v)$ be the set of $t$-cliques of $G$ that contain $v$. Then
$|R(v)|\leq\binom{d(v)}{t-1}$. Since $P$ is a longest path, $v$ and $w$ have
no neighbors outside of $P$, and so every $t$-clique in $R(v)$ is contained in
$V(P)$. Every $T\in R(v)$ has $p^{\prime}_{G}(T)=1/\binom{r-1}{t-2}$ because
it is contained in $P$ (and there are no longer paths). As noted above, we
have $\beta_{G-v}(T)\leq\beta_{G}(T)$ for any $T\in\mathcal{K}^{t}(G-v)$ and
as $p^{\prime}_{G}$ is also decreasing in $\beta_{G}(T)$,
$p^{\prime}_{G-v}(T)\geq p^{\prime}_{G}(T)$. Applying the inductive hypothesis
to $G-v$, we get

$\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}p^{\prime}_{G}(T)$
$\displaystyle=\sum_{T\in\mathcal{K}^{t}(G-v)}p^{\prime}_{G}(T)+\sum_{T\in
R(v)}p^{\prime}_{G}(T)$
$\displaystyle\leq\sum_{T\in\mathcal{K}^{t}(G-v)}p^{\prime}_{G-v}(T)+\sum_{T\in
R(v)}p^{\prime}_{G}(T)$
$\displaystyle\leq\frac{m-d(v)}{\binom{t}{2}}+\frac{|R(v)|}{\binom{r-1}{t-2}}$
$\displaystyle\leq\frac{m-d(v)}{\binom{t}{2}}+\frac{\binom{d(v)}{t-1}}{\binom{r-1}{t-2}}$
$\displaystyle=\frac{m-d(v)}{\binom{t}{2}}+\frac{\binom{d(v)-1}{t-2}}{\binom{r-1}{t-2}}\cdot\frac{d(v)}{t-1}$
$\displaystyle\leq\frac{m-d(v)}{\binom{t}{2}}+\frac{\binom{r/2-1}{t-2}}{\binom{r-1}{t-2}}\cdot\frac{d(v)}{t-1}$
$\displaystyle\leq\frac{m-d(v)}{\binom{t}{2}}+\frac{(1/2)^{t-2}\binom{r-2}{t-2}}{\binom{r-1}{t-2}}\cdot\frac{d(v)}{t-1}$
by 2.1
$\displaystyle=\frac{m-d(v)}{\binom{t}{2}}+\frac{r-t+1}{r-1}\cdot\frac{1}{2^{t-1}}\cdot\frac{d(v)}{\frac{t-1}{2}}$
$\displaystyle<\frac{m-d(v)}{\binom{t}{2}}+\frac{d(v)}{\binom{t}{2}}$
$\displaystyle=\frac{m}{\binom{t}{2}}$

as $2^{t-1}>t$ and $\frac{r-t+1}{r-1}<1$ when $t\geq 3$. Thus, if equality
holds, no component is in Case 4.4.2, so every component is in Case 4.4.1, and
every component is a clique. ∎

As mentioned, Chakraborti and Chen [8] determined
$\operatorname{\mathrm{mex}}(m,K_{t},P_{r+1})$ exactly, from which one can
derive the following weaker result:

######  Theorem 4.5 (Chakraborti and Chen [8]).

For any $3\leq t\leq r$, if $G$ is a $P_{r+1}$-free graph with $m$ edges, then

$\mathcal{N}(K_{t},G)\leq\frac{m}{\binom{r}{2}}\cdot\binom{r}{t}.$

Furthermore, equality holds if and only if $\binom{r}{2}$ divides $m$, and $G$
is a disjoint union of copies of $K_{r}$.

We use Theorem 4.4 to prove Theorem 4.5:

###### Proof.

Let $G$ be a $P_{r+1}$-free graph. Then for each $T\in\mathcal{K}^{t}(G)$, we
have $\beta_{G}(T)\leq r-1$ and as $p^{\prime}_{G}(T)$ is decreasing in
$\beta_{G}$,

$\mathcal{N}(K_{t},G)\cdot\frac{1}{\binom{r-2}{t-2}}\leq\sum_{T\in\mathcal{K}^{t}(G)}p^{\prime}_{G}(T)\leq\frac{m}{\binom{t}{2}}$

and therefore

$\mathcal{N}(K_{t},G)\leq\frac{m}{\binom{t}{2}}\cdot\binom{r-2}{t-2}=\frac{m}{\binom{r}{2}}\cdot\binom{r}{t}.$

Equality implies $G$ is a disjoint union of $P_{r+1}$-free complete graphs,
and every $t$-clique is contained in a $P_{r}$, so $G$ is a disjoint union of
copies of $K_{r}$. ∎

##  5 Weighting by Maximum Star Size

###  5.1 Graphs

In this section we consider generalized extremal problems of the form
$\mathrm{ex}(n,H,S_{r})$, forbidding the star with $r$ leaves. Unlike in
previous sections where $H$ was a clique, here we consider a broader range of
graphs $H$. We use $\mathcal{H}(G)$ to denote the set of (not necessarily
induced) subgraphs of $G$ isomorphic to $H$.

Given a graph $G$ and a non-empty set of vertices $U\subseteq V(G)$, the
_common neighborhood_ of $U$ in $G$ is the set of vertices of $G$ adjacent to
each vertex in $U$, or equivalently the intersection of the neighbor sets of
each vertex of $U$. The common degree of $U$, which we denote by
$\operatorname{cd}_{G}(U)$, is the size of the common neighborhood. Note that
$U$ is disjoint from its common neighborhood.

Denote the collection of dominating vertices of a graph $G$ by
$\operatorname{Dom}(G)$, and let
$\operatorname{dom}(G)=|\operatorname{Dom}(G)|$. Note that for any
$U\subseteq\operatorname{Dom}(G)$, $U$ is a clique, and the common
neighborhood of $U$ is $V(G)\setminus U$. Additionally, if
$U,U^{\prime}\subseteq\operatorname{Dom}(G)$ and $|U|=|U^{\prime}|$, then
$G-U\cong G-U^{\prime}$. For $u\leq\operatorname{dom}(G)$, we write
$G^{\downarrow u}$ to denote the graph that results from removing $u$
dominating vertices from $G$.

The main result of this section, 5.1, provides a template for localized bounds
on the number of copies of $H$ in a graph based on the number of sets of
dominating vertices of a given size contained in $H$. We will focus on the
cases where these sets have size one or two, but we provide the theorem in
full generality.

######  Theorem 5.1.

Let $H$ be a graph on $t$ vertices with $\operatorname{dom}(H)\geq 1$. For
every graph $G$ and each $T\in\mathcal{H}(G)$, define

$\theta_{G}(T)=\max\\{k:\exists v\in V(T)\subseteq V(S)\
\text{s.t.}\,V(S)\subseteq N[v]\text{ and }S_{k}\cong S\subseteq
G\\}=\max\\{d_{G}(v):v\in\operatorname{Dom}(T)\\},$

and for each $1\leq u\leq\operatorname{dom}(H)$, define

$s^{u}_{G}(T)=\frac{1}{\binom{\theta_{G}(T)-u+1}{t-u}}.$

Then for any $1\leq u\leq\operatorname{dom}(H)$, $s_{G}^{u}(T)$ is well-
defined and decreasing in $\theta_{G}(T)$, and

$\sum_{T\in\mathcal{H}(G)}s^{u}_{G}(T)\leq\frac{\mathcal{N}(H^{\downarrow
u},K_{t-u})}{\binom{\operatorname{dom}(H)}{u}}\cdot\mathcal{N}(K_{u},G).$

Furthermore, equality holds

  * •

if and only if $G$ has minimum degree at least $t-1$, if $H=S_{t-1}$ for some
$t\geq 3$,

  * •

if and only if $G$ contains no isolated vertices and every component of $G$ is
regular, if $u=1$ and $H=S_{1}$, and

  * •

if and only if every component of $G$ that contains a $u$-clique is a complete
graph on at least $t$ vertices, if $u\geq 2$ or $H$ is not a star.

###### Proof.

First, in any $T\in\mathcal{H}(G)$, there is a dominating vertex $v$ of $T$
which is the center of a star with (at least) $t-1$ leaves, so
$\theta_{G}(T)\geq t-1$ and $\binom{\theta_{G}(T)-u+1}{t-u}>0$. Therefore
$s^{u}_{G}(T)$ is well-defined and decreasing on $\theta_{G}(T)$.

Let $T\in\mathcal{H}(G)$ and $U\subseteq\operatorname{Dom}(T)$ such that
$|U|=u$. Recall $U$ is a clique. Thus for any $v\in U$, the vertices in the
common neighborhood of $U$ in $G$, together with the vertices
$U\setminus\\{v\\}$, are each adjacent to $v$, forming a copy of
$S_{\operatorname{cd}_{G}(U)+u-1}$ whose center is $v\in V(T)$ and which
contains all vertices of $T$ (because $v\in U\subseteq\operatorname{Dom}(T)$).
Therefore we have $\theta_{G}(T)\geq\operatorname{cd}_{G}(U)+u-1$, or
$\theta_{G}(T)-u+1\geq\operatorname{cd}_{G}(U)$.

For each $T\in\mathcal{H}(G)$, there are $\binom{\operatorname{dom}(H)}{u}$
sets $U\in\mathcal{K}^{u}(G)$ such that each vertex of $U$ is dominating in
$T$. For each $U\in\mathcal{K}^{u}(G)$, the number of copies $T$ of $H$ in $G$
for which $U\subseteq\operatorname{Dom}(T)$ is at most
$\binom{\operatorname{cd}_{G}(U)}{t-u}\mathcal{N}(H^{\downarrow u},K_{t-u})$:
we choose $t-u$ vertices from the common neighborhood of $U$ in $G$ to fill
out $T$ and then choose how to embed the vertices of $H^{\downarrow u}$, which
can be done in at most as many ways as embedding them into a clique of the
same size. Therefore

$\displaystyle\binom{\operatorname{dom}(H)}{u}\sum_{T\in\mathcal{H}(G)}s^{u}_{G}(T)$
$\displaystyle=\sum_{U\in\mathcal{K}^{u}(G)}\sum_{\begin{subarray}{c}T\in\mathcal{H}(G)\\\
U\subseteq\operatorname{Dom}(T)\end{subarray}}s^{u}_{G}(T)$
$\displaystyle=\sum_{U\in\mathcal{K}^{u}(G)}\sum_{\begin{subarray}{c}T\in\mathcal{H}(G)\\\
U\subseteq\operatorname{Dom}(T)\end{subarray}}\frac{1}{\binom{\theta_{G}(T)-u+1}{t-u}}$
$\displaystyle\leq\sum_{U\in\mathcal{K}^{u}(G)}\sum_{\begin{subarray}{c}T\in\mathcal{H}(G)\\\
U\subseteq\operatorname{Dom}(T)\end{subarray}}\frac{1}{\binom{\operatorname{cd}_{G}(U)}{t-u}}$
(1) $\displaystyle\leq\sum_{U\in\mathcal{K}^{u}(G)}\mathcal{N}(H^{\downarrow
u},K_{t-u})\frac{\binom{\operatorname{cd}_{G}(U)}{t-u}}{\binom{\operatorname{cd}_{G}(U)}{t-u}}$
(2) $\displaystyle=\mathcal{N}(H^{\downarrow u},K_{t-u})\mathcal{N}(K_{u},G).$

which establishes the inequality for all graphs $G$.

We now consider when equality holds in the bound. For ease of discussion, if
$U$ is contained in a copy $T$ of $H$ such that
$U\subseteq\operatorname{Dom}(T)$, we say that $T$ is an extension of $U$.
Equality in the bound requires equality in equations (1) and (2). In order for
equality to hold in (1), every pair $(U,T)$ where $T$ is an extension of $U$
must satisfy $\operatorname{cd}_{G}(U)=\theta_{G}(T)-u+1$. Equality in (2)
requires two conditions: first, for every $U\in\mathcal{K}^{u}(G)$, $G$ must
contain an extension of $U$ as otherwise this choice of $U$ contributes

$\sum_{\begin{subarray}{c}T\in\mathcal{H}(G)\\\
U\subseteq\operatorname{Dom}(T)\end{subarray}}\frac{1}{\binom{\operatorname{cd}_{G}(U)}{t-u}}=0$

instead of

$\sum_{\begin{subarray}{c}T\in\mathcal{H}(G)\\\
U\subseteq\operatorname{Dom}(T)\end{subarray}}\frac{1}{\binom{\operatorname{cd}_{G}(U)}{t-u}}=\mathcal{N}(H^{\downarrow
u},K_{t-u})>0.$

In particular, if equality holds in (2), $\operatorname{cd}_{G}(U)\geq t-u$
for every $U\in\mathcal{K}^{u}(G)$. Additionally, every $(t-u)$-set in the
common neighborhood of $U$ must contain $\mathcal{N}(H^{\downarrow
u},K_{t-u})$ copies of $H^{\downarrow u}$, or equivalently, the common
neighborhood of $U$ must contain the same number of copies of $H^{\downarrow
u}$ as a clique of the same size.

For each of the three cases delineated in the theorem, we consider the
conditions under which equality holds.

######  Case 5.1.1.

Suppose $H=S_{t-1}$ for some $t\geq 3$.

In this case we have $\operatorname{dom}(H)=1$ and thus $u=1$. This means that
for any $U\in\mathcal{K}^{u}(G)$, there is $v\in V(G)$ such that $U=\\{v\\}$,
and we have $\operatorname{cd}_{G}(U)=d_{G}(v)$. For any copy $T$ of $H$ in
$G$, there is a unique $U\subseteq\operatorname{Dom}(T)$ of size $u=1$, and if
$U=\\{v\\}$, then $\theta_{G}(T)=d_{G}(v)=\operatorname{cd}_{G}(U)$. We
conclude that equality holds in (1) for every graph $G$. If $w$ is the center
of $H=S_{t-1}$, then $H-w=H^{\downarrow 1}$ is an independent set, so
$\mathcal{N}(H^{\downarrow 1},K_{t-1})=1$. For any graph $G$ and any $v\in
V(G)$, if $d_{G}(v)\geq t-1$, then the number of copies $T$ of $H$ with $v$ at
the center is exactly
$\binom{d_{G}(v)}{t-1}=\binom{\operatorname{cd}_{G}(U)}{t-1}$ and equality
holds in (2). If $G$ has minimum degree at least $t-1$ then equality holds for
every vertex, so equality holds in the bound. On the other hand, if
$d_{G}(v)<t-1$ for any $v\in V(G)$, then there are no extensions of $\\{v\\}$
and equality does not hold in (2). As equality in the bound requires equality
for each $U\in\mathcal{K}^{u}(G)$, we conclude equality holds in this case if
and only if $d_{G}(v)\geq t-1$ for every $v\in V(G)$, which is to say $G$ has
minimum degree at least $t-1$.

######  Case 5.1.2.

Suppose $u=1$ and $H=S_{1}$.

This case is similar to 5.1.1: we have $u=1$, so the set of $u$-cliques of $G$
corresponds to the vertices of $G$, $H^{\downarrow 1}$ is an independent set
so $\mathcal{N}(H^{\downarrow 1},K_{t-1})=1$, and equality holds in (2) if and
only if each vertex has degree at least $t-1=2-1$, i.e. $G$ contains no
isolated vertices. The difference between the cases is that
$\operatorname{dom}(H)=2$ when $H=S_{1}$, and therefore rather than being
determined by the degree of a single vertex,

$\theta_{G}(T=\\{u,v\\})=\max\\{d_{G}(u),d_{G}(v)\\}.$

This introduces a circumstance in which equality may not hold in (1): if
$T=\\{u,v\\}$ and $d_{G}(u)>d_{G}(v)$, then for $U=\\{v\\}$,

$\frac{1}{\binom{\theta_{G}(T)}{t-u}}=\frac{1}{d_{G}(u)}<\frac{1}{d_{G}(v)}=\frac{1}{\binom{\operatorname{cd}_{G}(U)}{t-u}}.$

Thus equality in (1) holds if and only if $d_{G}(u)=d_{G}(v)$ for every
$T=\\{u,v\\}$, which is to say each component of $G$ is regular. We conclude a
graph $G$ meets the bound if and only if $G$ contains no isolated vertices and
each component of $G$ is regular.

######  Case 5.1.3.

Suppose $u\geq 2$ or that $H$ is not a star.

First we prove the given conditions are sufficient to achieve the bound. When
$G$ is a disjoint union of complete graphs on at least $t$ vertices and any
number of components without $u$-cliques, let $K_{r}$, $r\geq t\geq u$, be a
component of $G$ that contains a $u$-clique. Then $\theta_{G}(T)=r-1$ for
every $T\in\mathcal{H}(K_{r})$, and $s_{G}^{u}(T)=1/\binom{r-u}{t-u}$. The
number of copies of $H$ in this component is
$\binom{r}{u}\binom{r-u}{t-u}\mathcal{N}(H^{\downarrow
u},K_{t-u})/\binom{\operatorname{dom}{H}}{u}$, which can be seen by first
choosing a $u$-clique of the $K_{r}$ to act as a selected set of $u$
dominating vertices of $H$, then choosing $t-u$ of the $r-u$ other vertices in
the same component, then choosing an embedding of $H^{\downarrow u}$ into
those vertices. Each copy of $H$ is counted this way once for each choice of
selected set of $u$ dominating vertices of $H$. Therefore

$\sum_{T\in\mathcal{H}(K_{r})}s_{G}^{u}(T)=\frac{1}{\binom{r-u}{t-u}}\binom{r}{u}\binom{r-u}{t-u}\mathcal{N}(H^{\downarrow
u},K_{t-u})/\binom{\operatorname{dom}(H)}{u}=\frac{\mathcal{N}(H^{\downarrow
u},K_{t-u})}{\binom{\operatorname{dom}(H)}{u}}\mathcal{N}(K_{u},K_{r}).$

Note that if a component $C$ of $G$ contains no $u$-cliques, it also contains
no copies of $T$, so we have

$\sum_{T\in\mathcal{H}(C)}s^{u}_{C}(T)=0=\mathcal{N}(K_{u},C),$

and thus $C$ does not contribute to either side of the bound. If
$C_{1},\ldots,C_{k}$ are the components of $G$ containing $u$-cliques, then

$\sum_{T\in\mathcal{H}(G)}s_{G}^{u}(T)=\sum_{i=1}^{k}\sum_{T\in\mathcal{H}(C_{i})}s_{C_{i}}^{u}(T)=\frac{\mathcal{N}(H^{\downarrow
u},K_{t-u})}{\binom{\operatorname{dom}(H)}{u}}\sum_{i=1}^{k}\mathcal{N}(K_{u},C_{i})=\frac{\mathcal{N}(H^{\downarrow
u},K_{t-u})}{\binom{\operatorname{dom}(H)}{u}}\mathcal{N}(K_{u},G).$

We conclude that any graph $G$ in which every component that contains a
$u$-clique is a complete graph on at least $t$ vertices meets the bound.

Now if $G$ is a graph meeting the bound, we prove every component of $G$
containing a $u$-clique must be a clique containing at least $t$ vertices. We
begin with three claims.

Claim 1: If $G$ is a graph meeting the bound and $U\in\mathcal{K}^{u}(G)$,
then each vertex in $V(G)\setminus U$ that is adjacent to some $v\in U$ must
be in the common neighborhood of $U$.

Suppose otherwise: there is $v\in U$ and $x$ not in the common neighborhood of
$U$ such that $x\sim v$. As $G$ meets the bound, equality holds in (2), so we
may assume there exists an extension $T$ of $U$. Note that $T\subseteq N[v]$.
As $v$ is adjacent the common neighborhood of $U$, each other vertex of $U$,
and $x$, we see

$\theta_{G}(T)=\max\\{d_{G}(w):w\in\operatorname{Dom}(T)\\}\geq
d_{G}(v)\geq\operatorname{cd}_{G}(U)+u-1+1>\operatorname{cd}_{G}(U)+u-1$

and equality does not hold in (1), contradicting that $G$ met the bound.

Claim 2: If $u\geq 2$, $G$ is a graph meeting the bound, and
$U\in\mathcal{K}^{u}(G)$, then $U$ and its common neighborhood form a clique
in $G$.

Suppose $v,w\in U$ and that $x$ and $y$ are vertices in the common
neighborhood of $U$ such that $x\not\sim y$. Define $U^{\prime}=U-v+x$. If
there are no extensions $T$ of $U^{\prime}$, then equality will not hold in
(2), so assume such a $T$ exists. Then $y$ is not in the common neighborhood
of $U^{\prime}$, as $y\not\sim x$, but $y\sim w\in U\cap U^{\prime}$, so by
the contrapositive of Claim 1, equality does not hold.

Claim 3: If $H^{\downarrow u}$ contains at least one edge, $G$ is a graph
meeting the bound, and $U\in\mathcal{K}^{u}(G)$, then $U$ and its common
neighborhood form a clique in $G$.

We prove the contrapositive. Assume that some $U\in\mathcal{K}^{u}(G)$ and its
common neighborhood do not form a clique in $G$. Let $a$ and $b$ be non-
adjacent vertices in the common neighborhood of $U$ and let $\\{x,y\\}$ be an
edge in $H^{\downarrow u}$. If $G$ contains no extensions $T$ of $U$, then
equality does not hold in (2), so we may assume such an extension does exist,
and therefore $\operatorname{cd}_{G}(U)\geq t-u=|V(H^{\downarrow u})|$ as the
common neighborhood of $U$ contains at least $V(T)\setminus U$. Therefore
there exists an injective function $f$ from $V(H^{\downarrow u})$ to the
common neighborhood of $U$ such that $f(x)=a$ and $f(y)=b$. Note that $f$ is
not a homomorphism, demonstrating that not every injective function from
$H^{\downarrow u}$ to the common neighborhood of $U$ is an injective
homomorphism. By contrast, every injective function from $H^{\downarrow u}$ to
a clique is an injective homomorphism. This means there are fewer injective
homomorphisms from $H^{\downarrow u}$ into the common neighborhood of $U$ than
into a clique of the same size. For any graphs $P$ and $Q$, the number of
injective homomorphisms from $P$ to $Q$ is equal to the number of
automorphisms of $P$ times the number of copies of $P$ in $Q$. Therefore there
are also fewer copies of $H^{\downarrow u}$ in the common neighborhood of $U$
than there are in a clique of the same size, so as mentioned when discussing
the conditions under which equality holds in (2), $G$ does not meet the bound.

We are now prepared to show that $G$ meets the bound only if every component
of $G$ containing a $u$-clique is a complete graph containing at least $t$
vertices. If $G$ is disconnected, we consider each component separately, and
if a component $C$ does not contain a $u$-clique, we have seen $C$ does not
contribute to either side of the bound and need not be considered. Therefore
we may assume $G$ is connected and contains a $u$-clique. Either $u\geq 2$, in
which case Claim 2 applies, or $u=1$ and $H$ is not a star. In this case, the
graph that remains after removing any one dominating vertex contains an edge,
so Claim 3 applies. In either case, any $u$-clique forms a clique with its
common neighborhood. Applying Claim 1 to each $u$-set of this clique, no
vertex outside of this clique can be adjacent to any vertex contained in the
clique, so $G$ is a complete graph. In order for equality to hold in (2),
there must be at least one extension $T$ of $U$, which requires this complete
graph to have at least $t$ vertices. ∎

####  5.1.1 Weighting $t$-cliques by maximum star size

By taking $H=K_{t}$ and $u\in\\{1,2\\}$ in 5.1 we obtain the following
corollaries. We note that Proposition 1 in [22] is the case $t=2$ of 5.2.

######  Corollary 5.2.

For every $n$-vertex graph $G$ and every clique size $t\geq 1$,

$\sum_{T\in\mathcal{K}^{t}(G)}s^{1}_{G}(T)=\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{\theta_{G}(T)}{t-1}}\leq\frac{n}{t}.$

When $t=2$, equality holds if and only if $G$ contains no isolated vertices
and each component of $G$ is regular. When $t\geq 3$, equality holds if and
only if $G$ is a disjoint union of complete graphs of order at least $t$.

###### Proof.

Let $G$ be a graph on $n$ vertices. We set $H=K_{t}$ and $u=1$ in 5.1, so
$s^{1}_{G}(T)=\frac{1}{\binom{\theta_{G}(T)}{t-1}}$. Any vertex $v$ of $K_{t}$
is a dominating vertex of $K_{t}$, so by 5.1 we have

$\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{\theta_{G}(T)}{t-1}}\leq\frac{\mathcal{N}(K_{t}^{\downarrow
1},K_{t-1})}{\binom{\operatorname{dom}(K_{t})}{1}}\cdot\mathcal{N}(K_{1},G)=\frac{n}{t}.$

When $t=2$, $H=K_{2}=S_{1}$, so the equality condition matches the $u=1$ and
$H=S_{1}$ case in 5.1. When $t\geq 3$, the equality condition holds as cliques
on $t\geq 3$ vertices are not stars and any non-empty component contains a
$1$-clique, i.e. a vertex. ∎

Note that taking $t=1$ in 5.2 gives the true, if trivial, statement that an
$n$-vertex graph $G$ has at most $n$ vertices, so equality holds for all
graphs.

######  Corollary 5.3.

For every $m$-edge graph $G$ and every clique size $t\geq 2$,

$\sum_{T\in\mathcal{K}^{t}(G)}s^{2}_{G}(T)=\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{\theta_{G}(T)-1}{t-2}}\leq\frac{m}{\binom{t}{2}}.$

When $t\geq 3$, equality holds if and only if $G$ is a disjoint union of
complete graphs of order at least $t$ and any number of isolated vertices.

###### Proof.

Let $G$ be a graph on $m$ edges. We set $H=K_{t}$ and $u=2$ in 5.1, so
$s^{2}_{G}(T)=\frac{1}{\binom{\theta_{G}(T)-1}{t-2}}$. Any two vertices of
$K_{t}$ are dominating vertices of $K_{t}$, so by 5.1 we have

$\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{\theta_{G}(T)-1}{t-2}}\leq\frac{\mathcal{N}(K_{t}^{\downarrow
2},K_{t-2})}{\binom{\operatorname{dom}(K_{t})}{2}}\cdot\mathcal{N}(K_{2},G)=\frac{m}{\binom{t}{2}}.$

As above, the equality condition holds as cliques on $t\geq 3$ vertices are
not stars. As edges are $2$-cliques, all other components must be isolated
vertices. ∎

Similar to 5.2, taking $t=2$ in 5.3 gives a true but trivial statement, namely
than an $m$-edge graph has at most $m$ edges, so equality holds for all
graphs.

5.2 and 5.3 in turn imply the following two known theorems on the maximum
number of $t$-cliques in bounded-degree graphs having a given number of
vertices or a given number of edges, respectively. These theorems have also
been proved using essentially the same argument as the one used in [26] to
give an upper bound on the total number of cliques of all sizes. The first
theorem determines $\mathrm{ex}(n,K_{t},S_{r})$ asymptotically.

######  Corollary 5.4 (Wood [26]).

Let $t\geq 1$ and $G$ be a graph on $n$ vertices having $\Delta(G)\leq r-1$.
Then

$\mathcal{N}(K_{t},G)\leq\frac{n}{r}\binom{r}{t}.$

For $t\geq 3$, equality holds if and only if $r\mathrel{\bigm{|}}n$ and $G$ is
a disjoint union of copies of $K_{r}$.

###### Proof.

Let $G$ be a graph on $n$ vertices with maximum degree at most $r-1$. Then
$\theta_{G}(T)\leq r-1$ for every $T\in\mathcal{K}^{t}(G)$. By 5.2 we have

$\frac{\mathcal{N}(K_{t},G)}{\binom{r-1}{t-1}}=\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{r-1}{t-1}}\leq\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{\theta_{G}(T)}{t-1}}\leq\frac{n}{t},$

so
$\mathcal{N}(K_{t},G)\leq\frac{n}{t}\binom{r-1}{t-1}=\frac{n}{r}\binom{r}{t}$.
If $t\geq 3$ and equality holds, then every component is a clique. As $G$ has
maximum degree at most $r-1$, these cliques have at most $r$ vertices. If some
$G$ meeting the bound had a component $C$ with $a<r$ vertices, then $G-C$
would be a graph on $n-a$ vertices with $\frac{n}{r}\binom{r}{t}-\binom{a}{t}$
copies of $K_{t}$. As $t\geq 3$, we have

$a\binom{r}{t}=\frac{ar}{t}\binom{r-1}{t-1}>\frac{ar}{t}\binom{a-1}{t-1}=r\binom{a}{t}$

and thus $\frac{a}{r}\binom{r}{t}>\binom{a}{t}$, so

$\frac{n}{r}\binom{r}{t}-\binom{a}{t}>\frac{n}{r}\binom{r}{t}-\frac{a}{r}\binom{r}{t}=\frac{n-a}{r}\binom{r}{t}$

which contradicts the bound. ∎

If we instead fix the number of edges, we determine
$\operatorname{\mathrm{mex}}(m,K_{t},S_{r})$ asymptotically.

######  Corollary 5.5 (Wood [26]).

Let $t\geq 2$ and $G$ be a graph on $m$ edges with $\Delta(G)\leq r-1$. Then

$\mathcal{N}(K_{t},G)\leq\frac{m}{\binom{r}{2}}\binom{r}{t}.$

For $t\geq 3$, equality holds if and only if $\binom{r}{2}\mathrel{\bigm{|}}m$
and $G$ is a disjoint union of copies of $K_{r}$ with any number of isolated
vertices.

###### Proof.

Let $G$ be a graph on $m$ edges with maximum degree at most $r-1$. Again
$\theta_{G}(T)\leq r-1$ for every $T\in\mathcal{K}^{t}(G)$. By 5.3 we have

$\frac{\mathcal{N}(K_{t},G)}{\binom{r-2}{t-2}}=\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{r-2}{t-2}}\leq\displaystyle\sum_{T\in\mathcal{K}^{t}(G)}\frac{1}{\binom{\theta_{G}(T)-1}{t-2}}\leq\frac{m}{\binom{t}{2}},$

so
$\mathcal{N}(K_{t},G)\leq\frac{m}{\binom{t}{2}}\binom{r-2}{t-2}=\frac{m}{\binom{r}{2}}\binom{r}{t}$.
If $t\geq 3$ and equality holds, then every component is a clique. As $G$ has
maximum degree at most $r-1$, these cliques have at most $r$ vertices. Suppose
some $G$ meeting the bound has a component $C$ with $a<\binom{r}{2}$ edges.
Then $a=\binom{x}{2}$ for some real number $x<r$, and $G-C$ is a graph on
$m-a$ edges with at least $\frac{m}{\binom{r}{2}}\binom{r}{t}-\binom{x}{t}$
copies of $K_{t}$ by 2.3. As $t\geq 3$, we have

$a\binom{r}{t}=\binom{x}{2}\binom{r}{t}=\frac{x(x-1)r(r-1)}{2t(t-1)}\binom{r-2}{t-2}>\frac{x(x-1)r(r-1)}{2t(t-1)}\binom{x-2}{t-2}=\binom{r}{2}\binom{x}{t}$

and thus $\frac{a}{\binom{r}{2}}\binom{r}{t}>\binom{x}{t}$, so

$\frac{m}{\binom{r}{2}}\binom{r}{t}-\binom{x}{t}>\frac{m}{\binom{r}{2}}\binom{r}{t}-\frac{a}{\binom{r}{2}}\binom{r}{t}=\frac{m-a}{\binom{r}{2}}\binom{r}{t}$

which contradicts the bound. ∎

####  5.1.2 Weighting copies of $H$ by maximum star size

As mentioned, we can apply Theorem 5.1 to a broader class of graphs $H$ than
just cliques. This allows us to prove novel asymptotic results on
$\mathrm{ex}(n,H,S_{r})$ for any $H$ with at least one dominating vertex and
on $\operatorname{\mathrm{mex}}(n,H,S_{r})$ for $H$ with at least two
dominating vertices:

######  Theorem 5.6.

Let $H$ be a graph on $t$ vertices.

  1. (i)

If $H$ has at least one dominating vertex, then

$\mathrm{ex}(n,H,S_{r})=(1-o(1))\mathcal{N}(H,\lfloor\tfrac{n}{r}\rfloor
K_{r}),$

and

  2. (ii)

if $H$ has at least two dominating vertices, then

$\operatorname{\mathrm{mex}}(m,H,S_{r})=(1-o(1))\mathcal{N}(H,\Big{\lfloor}\tfrac{m}{\binom{r}{2}}\Big{\rfloor}K_{r}).$

###### Proof.

Let $G$ be an $S_{r}$-free graph on $n$ vertices and $m$ edges. Then for each
$T\in\mathcal{H}(G)$, we have $\theta_{G}(T)\leq r-1$ and thus
$s^{1}_{G}(T)\geq 1/\binom{r-1}{t-1}$ and $s^{2}_{G}(T)\geq
1/\binom{r-2}{t-2}$. Therefore, as long as $\operatorname{dom}(H)\geq 1$, let
$v$ be a dominating vertex and apply Theorem 5.1 with $u=1$ to get

$\mathcal{N}(H,G)\cdot\frac{1}{\binom{r-1}{t-1}}\leq\sum_{T\in\mathcal{H}(G)}s^{1}_{G}(T)\leq\frac{\mathcal{N}(H^{\downarrow
1},K_{t-1})}{\operatorname{dom}(H)}\cdot n$

so that

$\mathcal{N}(H,G)\leq n\binom{r-1}{t-1}\frac{\mathcal{N}(H^{\downarrow
1},K_{t-1})}{\operatorname{dom}(H)}=(1-o(1))\mathcal{N}(H,\lfloor\tfrac{n}{r}\rfloor
K_{r}),$

as, when $r\mid n$, we can count copies of $H$ in $\lfloor\frac{n}{r}\rfloor
K_{r}$ by first choosing a vertex $v$ of $G$ to act as a selected dominating
vertex in $H$, then choosing $t-1$ of the $r-1$ other vertices in the same
component, then choosing an embedding of $H^{\downarrow 1}$ into those
vertices (which is independent of the choice of $v$). Each copy of $H$ is
counted this way once for each choice of selected dominating vertex in $H$.
The asymptotic factor allows for $n$ not divisible by $r$. Furthermore, as
long as $\operatorname{dom}(H)\geq 2$, let $v$ and $w$ both be dominating
vertices and apply Theorem 5.1 with $u=2$ to get

$\mathcal{N}(H,G)\cdot\frac{1}{\binom{r-2}{t-2}}\leq\sum_{T\in\mathcal{H}(G)}s^{2}_{G}(T)\leq\frac{\mathcal{N}(H^{\downarrow
2},K_{t-1})}{\operatorname{dom}(H)}\cdot m$

so that

$\mathcal{N}(H,G)\leq m\binom{r-2}{t-2}\frac{\mathcal{N}(H^{\downarrow
2},K_{t-1})}{\operatorname{dom}(H)}=(1-o(1))\mathcal{N}(H,\Big{\lfloor}\tfrac{m}{\binom{r}{2}}\Big{\rfloor}K_{r}),$

where similarly the asymptotic factor allows for $m$ not divisible by
$\binom{r}{2}$.

In both cases we achieve a matching lower bound by taking as many disjoint
copies of $K_{r}$ as possible and making the remaining vertices independent or
making the remaining edges a matching. (For the values of $n$ and $m$ when we
have some remaining vertices or edges, a better lower bound is given by
forming a clique with the remaining vertices or a colex graph with the
remaining edges.) ∎

Notice that cliques, stars, and all connected threshold graphs have at least
one dominating vertex so are included as possible graphs $H$ in part $(i)$ of
5.6.

###  5.2 Hypergraphs

We now consider localized bounds for hypergraphs of bounded degree. Recall
that a hypergraph is _$q$ -uniform_ if every edge is a set of $q$ vertices.
The degree of a set of vertices $I$, denoted by $d(I)$, is the number of edges
$E$ that contain $I$. Letting $i=|I|$, the neighborhood of $I$ is the
$(q-i)$-uniform hypergraph $\\{E\setminus I:I\subset E\in E(\mathcal{H})\\}$.
For a $q$-uniform hypergraph $\mathcal{H}$ and $1\leq i<q$, we write
$\Delta_{i}(\mathcal{H})$ for the maximum degree $d(I)$ over all sets $I$ of
$i$ vertices.

For $t\geq q$, we denote by $K^{(q)}_{t}$ the complete $q$-uniform hypergraph
on $t$ vertices. We write $\mathcal{K}^{t}(\mathcal{H})$ for the set of
$t$-cliques in $\mathcal{H}$, i.e.,
$\mathcal{K}^{t}(\mathcal{H})=\\{S\subseteq V(\mathcal{H}):\mathcal{H}[S]\cong
K^{(q)}_{t}\\}$. We use the following upper bound on
$\mathcal{N}(K^{(q)}_{t},\mathcal{H})$, which is proved in [19, Theorem 32] as
an immediate consequence of Lovász’ approximate version of the Kruskal-Katona
theorem.

######  Theorem 5.7 (Lovász [20]).

Let $q,t\in\mathbb{N}$ with $t\geq q$. Let $\mathcal{H}$ be a $q$-uniform
hypergraph. Write the number of edges of $\mathcal{H}$ in the form
$\binom{x}{q}$, where $x\geq q-1$ is real. Then
$\mathcal{N}(K^{(q)}_{t},\mathcal{H})\leq\binom{x}{t}$.

The following theorem generalizes 5.2 to $q$-uniform hypergraphs. Note that
when $q=2$, we have $i=1$ and $x(I)=d(I)+i=d(v)+1$ for $I=\\{v\\}$, and so the
function $s(T)$ in the following theorem can be thought of as an extension of
the function $s_{G}^{1}(T)$ of Theorem 5.1 to hypergraphs.

######  Theorem 5.8.

Let $t\geq q>i\geq 1$ and suppose $\mathcal{H}$ is a $q$-uniform hypergraph on
$n$ vertices. For each $I\in\binom{V(\mathcal{H})}{i}$, define $x(I)\geq
q-i-1$ by the equation $d(I)=\binom{x(I)-i}{q-i}$, and, for each
$T\in\mathcal{K}^{t}(\mathcal{H})$, define

$x(T)=\max\Big{\\{}x(I):I\in\binom{T}{i}\Big{\\}}\quad\text{and}\quad
s(T)=\frac{1}{\binom{x(T)-i}{t-i}}.$

Then $s(T)$ is well-defined and decreasing as a function of $x(T)$,

$\sum_{T\in\mathcal{K}^{t}(\mathcal{H})}s(T)\leq\frac{\binom{n}{i}}{\binom{t}{i}},$

and there is an infinite family of hypergraphs that achieve the bound.

###### Proof.

Let $I\in\binom{V(\mathcal{H})}{i}$. For every $T\in\mathcal{K}^{t}(I)$, we
have $x(T)\geq x(I)$ by definition. If $\mathcal{K}^{t}(I)$ is nonempty, then
$d(I)\geq\binom{t-i}{q-i}$ and $x(I)\geq t$. Therefore every
$T\in\mathcal{K}^{t}(\mathcal{H})$ has $x(T)\geq t$, so $w(T)$ is a decreasing
function of $x(T)$. Hence $T\in\mathcal{K}^{t}(I)$ implies $w(T)\leq
1/\binom{x(I)-i}{t-i}$. Therefore

$\displaystyle\binom{t}{i}\sum_{T\in\mathcal{K}^{t}(\mathcal{H})}s(T)$
$\displaystyle=\sum_{I\in\binom{V(\mathcal{H})}{i}}\sum_{T\in\mathcal{K}^{t}(I)}s(T)$
$\displaystyle\leq\sum_{I\in\binom{V(\mathcal{H})}{i}}\sum_{T\in\mathcal{K}^{t}(I)}\frac{1}{\binom{x(I)-i}{t-i}}$
$\displaystyle\leq\sum_{I\in\binom{V(\mathcal{H})}{i}}\frac{\binom{x(I)-i}{t-i}}{\binom{x(I)-i}{t-i}}$
$\displaystyle=\binom{n}{i},$

where the second inequality follows from applying 5.7 to the neighborhood of
$I$.

Design theory provides an infinite family of graphs that meet this bound; we
direct the reader to [19] for more information on such hypergraphs. If
$\mathcal{H}$ is a $q$-shadow of a Steiner system $S(i,r,n)$ for some $r$ then
by [19, Lemma 38(b)] we have $x(I)=r$ for every $I$ and $x(T)=r$ for every
$T$, so $s(T)=\frac{1}{\binom{r-i}{t-i}}$. By [19, Lemma 38(a)] we have
$\mathcal{N}(K^{(q)}_{t},\mathcal{H})=\binom{r}{t}\frac{\binom{n}{i}}{\binom{r}{i}}$.
Therefore

$\sum_{T\in\mathcal{K}^{t}(\mathcal{H})}s(T)=\frac{\binom{r}{t}\binom{n}{i}}{\binom{r}{i}\binom{r-i}{t-i}}=\frac{\binom{n}{i}}{\binom{t}{i}}.\qed$

It seems interesting and challenging to characterize all of the extremal
$q$-graphs in 5.8. See [19, Theorem 43] for a related characterization of the
extremal $q$-graphs in the non-localized theorem.

As a corollary of 5.8 we obtain the following theorem of Radcliffe and the
first author on maximizing the number of $t$-cliques among bounded-degree
$q$-uniform hypergraphs.

######  Theorem 5.9 (Kirsch and Radcliffe [19]).

Let $1\leq i<q\leq t$ and suppose $\mathcal{H}$ is an $q$-uniform hypergraph
on $n$ vertices such that $\Delta_{i}(\mathcal{H})\leq\binom{x-i}{q-i}$ for
some real number $x\geq q$. Then

$\mathcal{N}(K^{(q)}_{t},\mathcal{H})\leq\frac{\binom{n}{i}}{\binom{x}{i}}\binom{x}{t}.$

###### Proof using 5.8.

The condition $\Delta_{i}(\mathcal{H})\leq\binom{x-i}{q-i}$ implies that
$x(I)\leq x$ for every $I\in\binom{V(\mathcal{H})}{i}$, so
$x(T)=\max\\{x(I):I\in\binom{T}{i}\\}\leq x$ for every
$T\in\mathcal{K}^{t}(\mathcal{H})$. 5.8 gives

$\frac{\mathcal{N}(K^{(q)}_{t},\mathcal{H})}{\binom{x-i}{t-i}}=\sum_{T\in\mathcal{K}^{t}(\mathcal{H})}\frac{1}{\binom{x-i}{t-i}}\leq\sum_{T\in\mathcal{K}^{t}(\mathcal{H})}w(T)\leq\frac{\binom{n}{i}}{\binom{t}{i}},$

so
$\mathcal{N}(K^{(q)}_{t},\mathcal{H})\leq\frac{\binom{n}{i}}{\binom{t}{i}}\binom{x-i}{t-i}=\frac{\binom{n}{i}}{\binom{x}{i}}\binom{x}{t}$.
∎

##  6 Open Problems

We briefly mention a few additional instances of problems that we believe are
amenable to localized extensions.

The following conjecture is a localized form of a theorem of Frohmader [13],
as phrased in [19, Theorem 8], on maximizing the number of $t$-cliques among
$m$-edge, $K_{r+1}$-free graphs.

######  Conjecture 6.1.

Let $t\geq 2$. For each $T\in\mathcal{K}^{t}(G)$, define

$\alpha_{G}(T)=\max\\{k:T\subseteq V(S)\textnormal{ for some }S\subseteq G\
\text{s.t.}\,S\cong K_{k}\\}\quad\text{and}\quad
w^{\prime}_{G}(T)=\frac{\binom{\alpha_{G}(T)}{2}^{t/2}}{\binom{\alpha_{G}(T)}{t}}.$

For every $m$-edge graph $G$,

$\sum_{T\in\mathcal{K}^{t}(G)}w^{\prime}_{G}(T)\leq m^{t/2}.$

After a preprint of this paper was made available, Aragão and Souza [2]
announced a proof of a generalization of 6.1.

Many extremal results on paths, beginning with the results of Erdős and Gallai
[12], are consequences of extremal theorems regarding cycles. While the family
of cycle graphs $\\{C_{3},C_{4},\ldots\\}$ does not have the subgraph
inclusion property shared by cliques, paths, and stars, these results consider
graphs of bounded circumference (that is, maximum cycle length). The
techniques in this paper often bounded a weight function by arguing a maximal
structure could not be extended; cycles do not allow such arguments, which
could make proving localized results more difficult. Nevertheless, we provide
the following weight function and conjectures based on results of Luo [21] and
Chakraborti and Chen [9], respectively.

######  Definition 6.2.

Let $t\geq 2$. For each $T\in\mathcal{K}^{t}(G)$, define

$\gamma_{G}(T)=\max\\{k:T\subseteq V(S)\textnormal{ for some }S\subseteq G\
\text{s.t.}\,S\cong C_{k}\\}.$

######  Conjecture 6.3.

Let $t\geq 2$. For each $T\in\mathcal{K}^{t}(G)$, define

$c_{G}(T)=\frac{\gamma_{G}(T)-1}{\binom{\gamma_{G}(T)}{t}}.$

Then $c_{G}(T)$ is well-defined and decreasing in $\gamma_{G}(T)$, and

$\sum_{T\in\mathcal{K}^{t}(G)}c_{G}(T)\leq n-1,$

with equality if and only if each $2$-connected component of $G$ is a complete
graph of order at least $t$.

######  Conjecture 6.4.

Let $t\geq 2$. For each $T\in\mathcal{K}^{t}(G)$, define

$c^{\prime}_{G}(T)=\frac{\binom{\gamma_{G}(T)}{2}}{\binom{\gamma_{G}(T)}{t}}.$

Then $c^{\prime}_{G}(T)$ is well-defined and decreasing in $\gamma_{G}(T)$,
and

$\sum_{T\in\mathcal{K}^{t}(G)}c^{\prime}_{G}(T)\leq m,$

with equality if and only if each $2$-connected component of $G$ is a complete
graph of order at least $t$ and any number of isolated vertices.

It may be possible to generalize 5.3 to hypergraphs. We make the following
conjecture as a localized version of Theorem 51 in [19], analogously to 5.8.

######  Conjecture 6.5.

Let $t\geq q>i\geq 1$ and suppose $\mathcal{H}$ is a $q$-uniform hypergraph on
$m$ edges. For each $I\in\binom{V(\mathcal{H})}{i}$, define $x(I)\geq q-i-1$
by the equation $d(I)=\binom{x(I)-i}{q-i}$, and, for each
$T\in\mathcal{K}^{t}(\mathcal{H})$, define

$x(T)=\max\Big{\\{}x(I):I\in\binom{T}{i}\Big{\\}}\quad\text{and}\quad
s^{\prime}(T)=\frac{1}{\binom{x(T)-q}{t-q}}.$

Then

$\sum_{T\in\mathcal{K}^{t}(\mathcal{H})}s^{\prime}(T)\leq\frac{m}{\binom{t}{q}}.$

Finally, we used 5.8 to obtain new asymptotically tight bounds on
$\mathrm{ex}(n,H,S_{r})$ when $H$ has at least one dominating vertex and on
$\operatorname{\mathrm{mex}}(m,H,S_{r})$ when $H$ has at least two dominating
vertices. It may be possible to prove similar results for hypergraphs.

######  Question 6.6.

Can 5.6 (or 5.1) be generalized to the setting of $q$-uniform hypergraphs with
bounded maximum $i$-degree, perhaps with $i=1$ or $i=q-1$, in such a way as to
obtain new generalized Turán-type results for hypergraphs?

## Acknowledgments

The authors thank Jamie Radcliffe for valuable discussions.

## References

  * [1] Noga Alon and Clara Shikhelman, _Many $T$ copies in $H$-free graphs_, J. Combin. Theory Ser. B 121 (2016), 146–172.
  * [2] Lucas Aragão and Victor Souza, _Localised graph Maclaurin inequalities_ , arXiv e-prints (2023), arXiv:2301.13189.
  * [3] József Balogh, Domagoj Bradač, and Bernard Lidický, _Weighted Turán theorems with applications to Ramsey-Turán type of problems_ , arXiv e-prints (2023), arXiv:2302.07859.
  * [4] József Balogh, Ce Chen, Grace McCourt, and Cassie Murley, _Ramsey-Turán Problems with small independence numbers_ , arXiv e-prints (2022), arXiv:2207.10545.
  * [5] Béla Bollobás, _Graph theory: an introductory course_ , vol. 63, Springer Science & Business Media, 2012.
  * [6] Béla Bollobás and Ervin Győri, _Pentagons vs. triangles_ , Discrete Mathematics 308 (2008), no. 19, 4332–4336.
  * [7] Domagoj Bradač, _A generalization of Turán’s theorem_ , arXiv e-prints (2022), arXiv:2205.08923.
  * [8] Debsoumya Chakraborti and Da Qi Chen, _Exact results on generalized Erdős-Gallai problems_ , arXiv e-prints (2020), arXiv:2006.04681.
  * [9] Debsoumya Chakraborti and Da Qi Chen, _Many cliques with few edges and bounded maximum degree_ , Journal of Combinatorial Theory, Series B 151 (2021), 1–20.
  * [10] Reinhard Diestel, _Extremal graph theory_ , Graph theory, Springer, 2017, pp. 173–207.
  * [11] Paul Erdős, _On the number of complete subgraphs contained in certain graphs_ , Magyar Tud. Akad. Mat. Kutató Int. Közl 7 (1962), no. 3, 459–464.
  * [12] Paul Erdős and Tibor Gallai, _On maximal paths and circuits of graphs_ , Acta Mathematica Hungarica 10 (1959), no. 3-4, 337–356.
  * [13] Andrew Frohmader, _Face vectors of flag complexes_ , Israel Journal of Mathematics 164 (2008), no. 1, 153–164.
  * [14] Dániel Gerbner, _Paths are Turán-good_ , arXiv e-prints (2022), arXiv:2204.07638.
  * [15] Dániel Gerbner and Cory Palmer, _Some exact results for generalized turán problems_ , European Journal of Combinatorics 103 (2022), 103519\.
  * [16] Lior Gishboliner and Asaf Shapira, _A generalized turán problem and its applications_ , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 760–772.
  * [17] Ervin Györi, János Pach, and Miklós Simonovits, _On the maximal number of certain subgraphs in $K_{r}$-free graphs_, Graphs and Combinatorics 7 (1991), no. 1, 31–37.
  * [18] Hamed Hatami, Jan Hladký, Daniel Král’, Serguei Norine, and Alexander Razborov, _On the number of pentagons in triangle-free graphs_ , Journal of Combinatorial Theory, Series A 120 (2013), no. 3, 722–732.
  * [19] Rachel Kirsch and Jamie Radcliffe, _Many cliques in bounded-degree hypergraphs_ , arXiv e-prints (2022), arXiv:2207.02336.
  * [20] L. Lovász, _Combinatorial problems and exercises_ , North-Holland Publishing Co., Amsterdam-New York, 1979.
  * [21] Ruth Luo, _The maximum number of cliques in graphs without long cycles_ , Journal of Combinatorial Theory, Series B 128 (2018), 219–226.
  * [22] David Malec and Casey Tompkins, _Localized versions of extremal problems_ , arXiv e-prints (2022), arXiv:2205.12246.
  * [23] Natasha Morrison, JD Nir, Sergey Norin, Paweł Rzażewski, and Alexandra Wesolek, _Every graph is eventually Turán-good_ , arXiv e-prints (2022), arXiv:2208.08499.
  * [24] Jamie Radcliffe and Andrew Uzzell, _Stability and Erdős–Stone type results for $F$-free graphs with a fixed number of edges_, arXiv e-prints (2018), arXiv:1810.04746.
  * [25] Paul Turán, _Eine Extremalaufgabe aus der Graphentheorie_ , Mat. Fiz. Lapok 48 (1941), 436–452.
  * [26] David R Wood, _On the maximum number of cliques in a graph_ , Graphs and Combinatorics 23 (2007), no. 3, 337–352.
  * [27] Alexander Aleksandrovich Zykov, _On some properties of linear complexes_ , Matematicheskii sbornik 66 (1949), no. 2, 163–188.