2024/07/06 by Li, Yongtao, Feng, Lihua, Peng, Yuejian · 3 citations
#05C35 #05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.04950
Recently, Ning and Zhai (2023) proved that every n-vertex graph G with λ(G) ≥ √(\lfloor n2/4\rfloor) has at least \lfloor n/2\rfloor -1 triangles, unless G=K\lceil (n)/(2) \rceil, \lfloor (n)/(2) \rfloor. The aim of this paper is two-fold. Using the supersaturation-stability method, we prove a stability variant of Ning-Zhai's result by showing that such a graph G contains at least n-3 triangles if no vertex is in all triangles of G. This result could also be viewed as a spectral version of a result of Xiao and Katona (2021). The second part concerns with the spectral supersaturation for the bowtie, which consists of two triangles sharing a common vertex. A theorem of Erdős, Füredi, Gould and Gunderson (1995) says that every n-vertex graph with more than \lfloor n2/4\rfloor +1 edges contains a bowtie. For graphs of given order, the spectral supersaturation problem has not been considered for substructures that are not color-critical. In this paper, we give the first such theorem by counting the number of bowties. Let K\lceil (n)/(2) \rceil, \lfloor (n)/(2) \rfloor+2 be the graph obtained from K\lceil (n)/(2) \rceil, \lfloor (n)/(2) \rfloor by embedding two disjoint edges into the vertex part of size \lceil (n)/(2) \rceil. Our result shows that every graph G with n≥ 8.8 × 106 vertices and λ(G)≥ λ(K\lceil (n)/(2) \rceil, \lfloor (n)/(2) \rfloor+2) contains at least \lfloor (n)/(2) \rfloor bowties, and K\lceil (n)/(2) \rceil, \lfloor (n)/(2) \rfloor+2 is the unique spectral extremal graph. This gives a spectral correspondence of a theorem of Kang, Makai and Pikhurko (2020). The method used in our paper provides a probable way to establish the spectral counting results for other graphs, even for non-color-critical graphs.