Vertex-Based Localization of Generalized Turán Problems

Abstract

Let $\mathcal{F}$ be a family of graphs. A graph is called $\mathcal{F}$-free if it does not contain any member of $\mathcal{F}$. Generalized Turán problems aim to maximize the number of copies of a graph $H$ in an $n$-vertex $\mathcal{F}$-free graph. This maximum is denoted by $ex(n,H,\mathcal{F})$. When $H\cong K_2$, it is simply denoted by $ex(n,F)$. Erdős and Gallai established the bounds $ex(n,P_{k+1})\le \frac{n(k-1)}{2}$ and $ex(n,C_{\ge k+1})\le \frac{k(n-1)}{2}$. This was later extended by Luo \cite{luo2018maximum}, who showed that $ex(n,K_s,P_{k+1})\le \frac{n}{k}\left(\genfrac{}{}{0ex}{}{k}{s}\right)$ and $ex(n,K_s,C_{\ge k+1})\le \frac{n-1}{k-1}\left(\genfrac{}{}{0ex}{}{k}{s}\right)$. Let $N(G,K_s)$ denote the number of copies of $K_s$ in $G$. In this paper, we use the vertex-based localization framework, introduced in \cite{adak2025vertex}, to generalize Luo's bounds. In a graph $G$, for each $v\in V(G)$, define $p(v)$ to be the length of the longest path that contains $v$. We show that \[N(G,K_s) \leq \sum_{v \in V(G)} \frac{1}{p(v)+1}{p(v)+1\choose s} = \frac{1}{s}\sum_{v \in V(G)}{p(v) \choose s-1}\] We strengthen the cycle bound from \cite{luo2018maximum} as follows: In graph $G$, for each $v\in V(G)$, let $c(v)$ be the length of the longest cycle that contains $v$, or $2$ if $v$ is not part of any cycle. We prove that \[N(G,K_s) \leq \left(\sum_{v\in V(G)}\frac{1}{c(v)-1}{c(v) \choose s}\right) - \frac{1}{c(u)-1}{c(u) \choose s}\] where $c(u)$ denotes the circumference of $G$. Furthermore, we characterize the class of extremal graphs that attain equality for these bounds. We provide full proofs for the cases $s=1$ and $s\ge 3$, while the case $s=2$ follows from the result in \cite{adak2025vertex}. We also conclude with a generalization of a result by Balister-Bollobás-Riordan-Schelp \cite{BALISTER2003366}.