Optimal spectral supersaturation for cliques and odd cycles

Source abstract

Let $Y_{n,r,q}$ be the graph obtained from the Turán 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 $χ(F)=r+1$, there exists a constant $δ_F>0$ such that for all sufficiently large $n$ and all $1\le q\le δ_F \sqrt{n}$, the condition $λ(G)\geλ(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 $δ_F$ remained unknown for any $F$. In this paper, building on a structural result of Fang, Li, Lin and Ma, we determine the threshold $δ_F$ when $F$ is a clique and an odd cycle. For every $r\ge2$, we denote $δ_r :=(1-\tfrac1r)\sqrt2$ and prove that for every $\varepsilon>0$, if $n$ is sufficiently large and $1\le q\le(δ_r-\varepsilon)\sqrt n$, then every $n$-vertex graph $G$ with $λ(G)\geλ(Y_{n,r,q})$ contains at least $q\,c(n,K_{r+1})$ copies of $K_{r+1}$, and $δ_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 $λ(G)\geλ(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ász and Simonovits, and $1/2$ for odd cycles by Pikhurko and Yilma.