Supersaturation in Nosal graphs: Triangles and books

Abstract

In this paper, we use the spectral surplus $\hat{I}»(G)-\sqrt{m}$ to measure how far $G$ lies above the Nosal threshold, and prove the following edge-spectral supersaturation results for triangles and books. (a) Every graph $G$ with $m\ge 3$ edges and $\hat{I}»(G)\ge 1+\sqrt{m-2}$ contains at least $m-2$ triangles, with equality if and only if $G=K_3\vee \frac{m-3}{3}{K}_1$. This can be viewed as the third-layer supersaturation in the jump phenomenon, after the first layer $t(G)\ge \lfloor \frac{1}{2}(\sqrt{m}-1)\rfloor$ proved by Ning and Zhai, and the second layer $t(G)\ge \frac{m-1}{2}$ by Zhang and Zhai. (b) Every $m$-edge graph $G$ satisfies $t(G)\ge m(\hat{I}»-\sqrt{m})$, with equality if and only if $G$ is complete bipartite. Consequently, $\hat{I}»(G)\ge \sqrt{m}+q$ forces $t(G)>qm$ for every real $q>0$. This is an edge-spectral counterpart of the Lovász--Simonovits theorem, and it improves the Bollobás--Nikiforov bound $t(G)\ge \frac{1}{3}\hat{I}»(\hat{I}{»}^2-m)$ in the range $\sqrt{m}\le \hat{I}»(G)\le 1.3\sqrt{m}$. (c) Every $m$-edge Nosal graph $G$ contains a book of size greater than $\frac{1}{4}\sqrt{m}$. This improves two recent results on the booksize constant: $\frac{1}{24}$ proved by Li, Liu and Zhang, and $\frac{1}{9}$ by Zhai, Li and Lou. This narrows the gap toward the conjectured optimal constant $\frac{1}{3}$. (d) Every $m$-edge Nosal graph $G$ contains at least $(\frac{1}{8}-o(1))m$ copies of the kite $C_4^{+}=B_2$, and the constant $\frac{1}{8}$ is best possible. This determines the sharp asymptotic constant for counting $C_4^{+}$ and strengthens the $\hat{I}\text{c◯}(m)$ bound of Li, Liu and Zhang.

31 pages, 1 figure. Spectral extremal graph theory