Spectral supersaturation for color-critical graphs

Abstract

A graph is color-critical if it contains an edge whose deletion reduces its chromatic number. This class of graphs, including cliques and odd cycles, plays a central role in extremal graph theory. In this paper, following an influential line of research initiated by Bollobás-Nikiforov, we study the spectral supersaturation problem for color-critical graphs. Let $T_{n,r}$ be the $r$-partite Turán graph, let ${\mathcal{T}}_{n,r,q}$ denote the family of graphs obtained from $T_{n,r}$ by adding $q$ edges, and let $\hat{I}»(G)$ be the spectral radius of a graph $G$. We first prove that for any color-critical graph $F$ with chromatic number $r+1$, there exists $\hat{I}{´}_F>0$ such that for sufficiently large $n$ and all $1\le q\le \hat{I}{´}_F\sqrt{n}$, any $n$-vertex graph $G$ with $\hat{I}»(G)\ge {\min }_{T\in {\mathcal{T}}_{n,r,q}}\hat{I}»(T)$ contains at least $q\cdot c(n,F)$ copies of $F$, where $c(n,F)$ denotes the minimum number of copies of $F$ created by adding a single edge to $T_{n,r}$; moreover, any extremal graph $G$ must belong to ${\mathcal{T}}_{n,r,q}$.Next, we prove a spectral supersaturation result for the analogous condition $\hat{I}»(G)\ge {\max }_{T\in {\mathcal{T}}_{n,r,q}}\hat{I}»(T)$, valid for all $1\le q\le \hat{I}{´}_{F}n$. Together, these results provide a complete resolution to a problem proposed by Ning-Zhai, and establish a spectral counterpart to the well-known results of Mubayi and Pikhurko-Yilma in the extremal supersaturation setting. A notable feature of our first result is that the restriction $q=O(\sqrt{n})$ is tight up to a constant factor, in contrast to the linear bounds provided by other settings discussed above. As applications, we extend a result of Liu-Mubayi, and solve a related conjecture by Li-Lu-Peng.

31 pages. Any suggestions are welcome