Unbalanced Turán and spectral Turán problems with prescribed large maximum degree

Abstract

Classical Turán-type problems determine the maximum number of edges and spectral radius of an $n$-vertex $F$-free graph without a degree constraint. We study the corresponding problems in the class of $n$-vertex $F$-free graphs $G$ with prescribed maximum degree $\Delta (G)=\Delta$. Let $\chi (F)=r+1\ge 3$ and $\lceil (r-1)n/r\rceil \le \Delta \le n-1$. The maximum-degree condition leads to the complete $r$-partite graph $S_{n,\Delta }^{(r)}=(n-\Delta )K_1\vee T(\Delta ,r-1)$, whose part of size $n-\Delta$ is generally smaller than the other parts; this is the source of the unbalanced Turán problem considered here. Let ${\mathrm{ex}}_F(n,\Delta )$ and ${\mathrm{spex}}_F(n,\Delta )$ denote the maximum number of edges and adjacency spectral radius, respectively, in this class. For $F=K_{r+1}$, we prove that $S_{n,\Delta }^{(r)}$ is the unique extremal graph for both parameters. For a general graph $F$, let $a(F)$ be the minimum size of an independent set $I$ such that $\chi (F-I)\le r$. If $a(F)=1$, we prove edge and spectral stability with respect to $S_{n,\Delta }^{(r)}$. If $a(F)>1$, the extremal values have the usual Erdős--Stone--Simonovits asymptotics, and the edge- and spectral-extremal graphs are $o(n^2)$-close to $T(n,r)$. Finally, for a finite forbidden family, we prove that a decomposition-family edge bound of order $O(n^{1+s})$ yields a spectral-radius bound with error term $O(n^s)$, where $0\le s<1$. This can be used to obtain spectral-radius estimates from decomposition-family bounds in other unbalanced Turán problems.