Exact Clique Counts in Graphs with a Forbidden Tree

Abstract

For a fixed tree $T$ on $t$ vertices, let $\ex(n,K_r,T)$ denote the maximum number of $r$-cliques in an $n$-vertex $T$-free graph. Write $n=\alpha (t-1)+\beta$ with $0\le \beta <t-1$. A conjecture proposed in extremal-graph form by Alon and Shikhelman~\cite{alon2016}, later stated explicitly as an exact clique-counting formula by Gerbner and Palmer~\cite{GP2026}, asserts that \[ \ex(n,K_r,T)=α\binom{t-1}{r}+\binomβr, \] with the extremal construction given by the vertex disjoint union of $\alpha$ copies of $K_{t-1}$ and a graph with $\beta$ vertices. This paper proves this conjecture for every $n$ and for every tree $T$ whenever $C\log t\le r\le t-1$ and $t$ is sufficiently large, where $C$ is an absolute constant. This lowers the previously known general threshold $r\ge \lceil (2t-1)/3\rceil$, which is linear in $t$ to logarithmic order. The paper also proves the conjecture for every $3\le r\le t-1$ when at least $\lceil (t-3)/2\rceil$ leaves of $T$ have a common neighbor, and this extends the known results for stars and double stars.

arXiv comment11 pages