Sharp Bounds for Guiduli-Type Hereditary Spectral Problems

Guiduli asked in 1996 the following problem concerning the maximum spectral radius of a graph under hereditary density constraints. If an $n$-vertex graph $G$ satisfies $e(H)\le c\mathrm{\mid }V(H){\mathrm{\mid }}^2$ for every subgraph $H$ of $G$, must one have $\lambda (G)\le 2cn$? More generally, what remains true when the exponent $2$ is replaced by a constant less than $2$? We study the natural power-law version of this question for all $1<p\le 2$. For $1<p\le 2$, define $$d_p(G)=\underset{\mathrm{\varnothing }\mathrm{\ne }S\subseteq V(G)}{\max }\frac{e(G[S])}{\mathrm{\mid }S{\mathrm{\mid }}^p}\mathrm{.}$$ We determine the sharp asymptotic upper bound for $\lambda (G)$ in terms of $d_p(G)$ and $n$. More precisely, every $n$-vertex graph $G$ with at least one edge satisfies $$\lambda (G)\le \{\begin{array}{ll}({\left({\max }_{t\in {\mathbb{N}}_{\ge 1}}{\displaystyle \frac{t}{(t+1{)}^p}}\right)}^{-1}+o(1))d_p(G)\sqrt{n},& 1<p<3\mathrm{/}2,\\ ({\displaystyle \frac{3\sqrt{3}}{4}}+o(1))d_p(G)\sqrt{n\log n},& p=3\mathrm{/}2,\\ ({\mathfrak{C}}_p+o(1))d_p(G)n^{p-1},& 3\mathrm{/}2<p<2,\end{array}$$ and each constant here is best possible. Here ${\mathfrak{C}}_p$ is characterized by an exact variational problem over finite kernels. We apply a sparse graphon operator estimate to convert hereditary $p$-density bounds into sharp spectral bounds, and this estimate also explains the transition at the critical exponent $p=3\mathrm{/}2$. For the endpoint $p=2$, Wilf’s theorem gives the exact finite-$n$ bound $\lambda (G)\le 2d_2(G)n$, with equality for $K_n$. Thus Guiduli’s power-law problem is resolved in its sharp asymptotic form for every $1<p\le 2$, including exact leading constants.