Counting substructures and eigenvalues I: triangles

DOI10.1016/J.EJC.2023.103685MaRDI QIDQ6386616arXivFDO

Authors Bo Ning, Mingqing Zhai

Publication date 23 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.EJC.2023.103685

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Enumeration in graph theory (05C30)

arXiv classification

math.CO

Abstract: Motivated by the counting results for color-critical subgraphs by Mubayi [Adv. Math., 2010], we study the phenomenon behind Mubayi's theorem from a spectral perspective and start up this problem with the fundamental case of triangles. We prove tight bounds on the number of copies of triangles in a graph with a prescribed number of vertices and edges and spectral radius. Let $n$ and $m$ be the order and size of a graph. Our results extend those of Nosal, who proved there is one triangle if the spectral radius is more than $sqrtm$, and of Rademacher, who proved there are at least $lfloorfracn2floor$ triangles if the number of edges is more than that of 2-partite Tur'an graph. These results, together with two spectral inequalities due to Bollob'as and Nikiforov, can be seen as a solution to the case of triangles of a problem of finding spectral versions of Mubayi's theorem. In addition, we give a short proof of the following inequality due to Bollob'as and Nikiforov [J. Combin. Theory Ser. B, 2007]: $t(G)geqfraclambda(G)(lambd{a}^2(G)-m)3$ and characterize the extremal graphs. Some problems are proposed in the end.

This page was built for publication: Counting substructures and eigenvalues I: triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6386616)