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

Source 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 $Δ(G)=Δ$. Let $χ(F)=r+1\ge3$ and $\lceil(r-1)n/r\rceil\leΔ\le n-1$. The maximum-degree condition leads to the complete $r$-partite graph $S_{n,Δ}^{(r)}=(n-Δ)K_1\vee T(Δ,r-1)$, whose part of size $n-Δ$ is generally smaller than the other parts; this is the source of the unbalanced Turán problem considered here. Let $\mathrm{ex}_F(n,Δ)$ and $\mathrm{spex}_F(n,Δ)$ denote the maximum number of edges and adjacency spectral radius, respectively, in this class. For $F=K_{r+1}$, we prove that $S_{n,Δ}^{(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 $χ(F-I)\le r$. If $a(F)=1$, we prove edge and spectral stability with respect to $S_{n,Δ}^{(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.