Almost regular subgraphs under spectral radius constrains

Abstract

A graph is called $K$-almost regular if its maximum degree is at most $K$ times the minimum degree. Erdős and Simonovits showed that for a constant $0<\epsilon <1$ and a sufficiently large integer $n$, any $n$-vertex graph with more than $n^{1+\epsilon }$ edges has a $K$-almost regular subgraph with $n^{\prime }\ge n^{\epsilon \frac{1-\epsilon }{1+\epsilon }}$ vertices and at least $\frac{2}{5}{n}^{\prime 1+\epsilon }$ edges. An interesting and natural problem is whether there exits the spectral counterpart to Erdős and Simonovits's result. In this paper, we will completely settle this issue. More precisely, we verify that for constants $\frac{1}{2}<\epsilon \le 1$ and $c>0$, if the spectral radius of an $n$-vertex graph $G$ is at least $c{n}^{\epsilon }$, then $G$ has a $K$-almost regular subgraph of order $n^{\prime }\ge n^{\frac{2{\epsilon }^2-\epsilon }{24}}$ with at least $c^{\prime }{n}^{\prime 1+\epsilon }$ edges, where $c^{\prime }$ and $K$ are constants depending on $c$ and $\epsilon$. Moreover, for $0<\epsilon \le \frac{1}{2}$, there exist $n$-vertex graphs with spectral radius at least $c{n}^{\epsilon }$ that do not contain such an almost regular subgraph. Our result has a wide range of applications in spectral Turán-type problems. Specifically, let $ex(n,\mathcal{H})$ and $spex(n,\mathcal{H})$ denote, respectively, the maximum number of edges and the maximum spectral radius among all $n$-vertex $\mathcal{H}$-free graphs. We show that for $1\ge \hat{I}¾>\frac{1}{2}$, $ex(n,\mathcal{H})=O(n^{1+\hat{I}¾})$ if and only if $spex(n,\mathcal{H})=O(n^{\hat{I}}¾)$.

9 pages