flâneur

[2408.01709] A spectral Lovász-Simonovits theorem

arxiv.org · 762 words · saved by 1 readers

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 $\lambda (G) \ge \lambda (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).

[2408.01709] A spectral Lovász-Simonovits theorem --> Mathematics > Combinatorics arXiv:2408.01709 (math) [Submitted on 3 Aug 2024 ( v1 ), last revised 18 Mar 2026 (this version, v2)] Title: A spectral Lovász-Simonovits theorem Authors: Yongtao Li , Lihua Feng , Yuejian Peng View a PDF of the paper titled A spectral Lov\'{a}sz-Simonovits theorem, by Yongtao Li and 2 other authors View PDF HTML (experimental) 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 c

saved by

related reading