Optimal spectral supersaturation for cliques and odd cycles

Abstract

Let $Y_{n,r,q}$ be the graph obtained from the Tur\'an graph $T_{n,r}$ by adding $q$ pairwise disjoint edges inside a largest part, and let $c(n,F)$ be the minimum number of copies of $F$ created by adding a single edge to $T_{n,r}$. Fang, Li, Lin and Ma proved that for every color-critical graph $F$ with $\chi (F)=r+1$, there exists a constant $\delta_F>0$ such that for all sufficiently large $n$ and all $1\le q\le \delta_F \sqrt{n}$, the condition $\lambda(G)\ge\lambda(Y_{n,r,q})$ forces at least $q\, c(n,F)$ copies of $F$. The bound $q=O(\sqrt{n}\,)$ is tight up to a constant factor, in contrast to the linear order $n$ of the edge setting of Mubayi, Pikhurko and Yilma, but the exact constant $\delta_F$ remained unknown for any $F$. In this paper, building on a structural result of Fang, Li, Lin and Ma, we determine the threshold $\delta_F$ when $F$ is a clique and an odd cycle. For every $r\ge2$, we denote $\delta_r :=(1-\tfrac1r)\sqrt2$ and prove that for every $\varepsilon>0$, if $n$ is sufficiently large and $1\le q\le(\delta_r-\varepsilon)\sqrt n$, then every $n$-vertex graph $G$ with $\lambda(G)\ge\lambda(Y_{n,r,q})$ contains at least $q\,c(n,K_{r+1})$ copies of $K_{r+1}$, and $\delta_r$ is best possible. For odd cycles, the threshold is $1/\sqrt2$. For every $k\ge1$ and $\varepsilon>0$, if $n$ is sufficiently large and $1\le q\le(1/\sqrt2-\varepsilon)\sqrt n$, then every $n$-vertex graph $G$ with $\lambda(G)\ge\lambda(Y_{n,2,q})$ contains at least $q\,c(n,C_{2k+1})$ copies of $C_{2k+1}$, and $1/\sqrt2$ is best possible. Our results determine both the exact count of copies and the optimal range of $q$. The behavior in the spectral setting differs from the classical edge setting, in which the range of $q$ is of order $n$ and the threshold is $1/r$ for cliques by Lov\'{a}sz and Simonovits, and $1/2$ for odd cycles by Pikhurko and Yilma.