On the large-clique version of the Erdős-Sós theorem

Abstract

For graphs $H$ and $F$, let $\mathrm{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $F$-free graph of order $n$. Motivated by the Erdős-Sós theorem, Gerbner and Palmer and, independently, Zhao and Peng conjectured that for every tree $T$ of order $k$ and every $3\le r\le k-1,$ $$\mathrm{ex}(n,K_r,T)=a\left(\genfrac{}{}{0ex}{}{k-1}{r}\right)+\left(\genfrac{}{}{0ex}{}{b}{r}\right),$$ where $n=a(k-1)+b$ with $0\le b<k-1$. In this paper, we confirm the conjecture for $r\ge \lceil (2k-1)/3\rceil$ and characterize all extremal graphs.

arXiv commentThe introduction has been slightly revised, as the Erdős-Sós conjecture was recently resolved