Counting substructures and eigenvalues. II: Quadrilaterals

Bo Ning ; Mingqing Zhai¹

¹Chuzhou University,Chuzhou, Ahhui, China

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

Let $G$ be a graph with $m$ edges and $\lambda(G)$ be the spectral radius of $G$. Nikiforov [Combin. Proba. Comput., 2002] proved that if $\lambda(G)>\sqrt{(1-\frac{1}{r})2m}$ then $G$ contains a $K_{r+1}$. Bollobás and Nikiforov [J. Combin. Theory Ser. B, 2007] proved some spectral counting results for cliques, which is a spectral Moon-Moser Inequality. Very recently, the present authors proved a counting result of spectral Rademacher Theorem for triangles. It is natural to consider counting results for classes of degenerate graphs. A previous result due to Nikiforov [Linear Algebra Appl., 2009] asserted that every graph $G$ on $m\geq 10$ edges contains a 4-cycle if $\lambda(G)>\sqrt{m}$. Define $f(m)$ to be the minimum number of copies of 4-cycles in such a graph. A consequence of a recent theorem due to Zhai et al. [European J. Combin., 2021] shows that $f(m)=\Omega(m)$. In this article, by somewhat different techniques, we prove that $f(m)=\Theta(m^2)$. We mention some problems for further study.

Détail

DOI : 10.37236/12725

Classification : 05C30, 05C50, 05C35
Mots-clés : color critical graph, Turán graph, removal lemma