Li, Yongtao; Feng, Lihua; Peng, Yuejian Spectral supersaturation: triangles and bowties. European J. Combin. 128 (2025), Paper No. 104171, 27 pp.

Release time:2025-10-28

Journal:European J. Combin.

Key Words:A classical result of Erdős and Rademacher (1955) demonstrates a fundamental supersaturation phenomenon in extremal combinatorics: every graph on n vertices with more than ⌊n2/4⌋ edges contains at least ⌊n/2⌋ triangles. Let λ(G) be the spectral radius of the adjacency matrix of a graph G. Recently, Ning and Zhai (2023) proved that every n-vertex graph G with λ(G)≥⌊n2/4⌋−−−−−−√ contains at least ⌊n/2⌋−1 triangles, unless G is a balanced complete bipartite graph K⌈n/2⌉,⌊n/2⌋. The aim of this paper is two-fold. Using a different approach which they term the supersaturation stability method, the authors prove a stability variant of the Ning-Zhai result by showing that such a graph G contains at least n−3 triangles if no vertex lies in all triangles of G. This bound is best possible and it could also be viewed as a spectral analogue of a theorem of Xiao and Katona (2021). The second part of the paper is concerned with the spectral supersaturation for the bowtie, which consists of two triangles sharing a vertex. The method developed in the paper could be helpful in establishing spectral results for counting other substructures, even for non-color-critical graphs.

Translation or Not:no

Included Journals:SCI