A spectral Lovász-Simonovits theorem

Abstract

A fundamental result in extremal graph theory is attributed to Mantel's theorem, which states that every graph on $n$ vertices with more than $\lfloor n^2/4\rfloor$ edges must contain a triangle. Lovász and Simonovits (1975) provided a supersaturation phenomenon by showing that for any $q<n/2$, every graph with $\lfloor n^2/4\rfloor +q$ edges contains at least $q\lfloor n/2\rfloor$ triangles. This result resolved a conjecture proposed by Erdős in 1962. In this paper, we establish a spectral counterpart of the result of Lovász and Simonovits. Let $Y_{n,2,q}$ be the graph obtained from the bipartite Turán graph $T_{n,2}$ by embedding a matching with $q$ edges into the partite set of size $\lceil n/2\rceil$. Using the supersaturation-stability method and the spectral techniques, we firstly prove that for $q\le \frac{1}{11}\sqrt{n}$, every graph $G$ on $n$ vertices with spectral radius $\hat{I}»(G)\ge \hat{I}»(Y_{n,2,q})$ contains at least $q\lfloor n/2\rfloor$ triangles. We also show that the bound $q=O(\sqrt{n})$ is tight up to a constant factor, yielding a phenomenon different from that in edge supersaturation. Our result answers a spectral triangle counting problem proposed by Ning and Zhai (2023). Secondly, let $T_{n,2,q}$ be the graph obtained from $T_{n,2}$ by embedding a star with $q$ edges into the partite set of size $\lceil n/2\rceil$. We show further that $T_{n,2,q}$ is the unique extremal graph that contains at most $q\lfloor n/2\rfloor$ triangles and attains the maximum spectral radius. Thirdly, we present an asymptotic spectral stability result under a specific constraint on the triangle covering number. This result could be viewed as a spectral extension of a recent result proved by Balogh and Clemen (2023), and independently by Liu and Mubayi (2022).

We improved the coefficients, and showed that the range of q is tight up to a constant factor. This phenomenon is different from that of edge supersaturation