The Generalized Turán Problem of Two Intersecting Cliques

Abstract

For $s<r$, let $B_{r,s}$ be the graph consisting of two copies of $K_r$, which share exactly $s$ vertices. Denote by $ex(n,K_r,B_{r,s})$ the maximum number of copies of $K_r$ in a $B_{r,s}$-free graph on $n$ vertices. In 1976, Erdős and Sós determined $ex(n,K_3,B_{3,1})$. Recently, Gowers and Janzer showed that $ex(n,K_r,B_{r,r-1})=n^{r-1-o(1)}$. It is a natural question to ask for $ex(n,K_r,B_{r,s})$ for general $r$ and $s$. In this paper, we mainly consider the problem for $s=1$. Utilizing the Zykov's symmetrization, we show that $ex(n,K_4,B_{4,1})=\lfloor (n-2{)}^2/4\rfloor$ for $n\ge 45$. For $r\ge 5$ and $n$ sufficiently large, by the Füredi's structure theorem we show that $ex(n,K_r,B_{r,1})=\mathcal{N}(K_{r-2},T_{r-2}(n-2))$, where $\mathcal{N}(K_{r-2},T_{r-2}(n-2))$ represents the number of copies of $K_{r-2}$ in the $(r-2)$-partite Turán graph on $n-2$ vertices.

20 pages,5 figures