Almost regular subgraphs under spectral radius constrains
| Autor: | Xu, Weilun, Gao, Guorong, Chang, An |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A graph is called $K$-almost regular if its maximum degree is at most $K$ times the minimum degree. Erd\H{o}s and Simonovits showed that for a constant $0< \varepsilon< 1$ and a sufficiently large integer $n$, any $n$-vertex graph with more than $n^{1+\varepsilon}$ edges has a $K$-almost regular subgraph with $n'\geq n^{\varepsilon\frac{1-\varepsilon}{1+\varepsilon}}$ vertices and at least $\frac{2}{5}n'^{1+\varepsilon}$ edges. An interesting and natural problem is whether there exits the spectral counterpart to Erd\H{o}s and Simonovits's result. In this paper, we will completely settle this issue. More precisely, we verify that for constants $\frac{1}{2}<\varepsilon\leq 1$ and $c>0$, if the spectral radius of an $n$-vertex graph $G$ is at least $cn^{\varepsilon}$, then $G$ has a $K$-almost regular subgraph of order $n'\geq n^{\frac{2\varepsilon^2-\varepsilon}{24}}$ with at least $ c'n'^{1+\varepsilon}$ edges, where $c'$ and $K$ are constants depending on $c$ and $\varepsilon$. Moreover, for $0<\varepsilon\leq\frac{1}{2}$, there exist $n$-vertex graphs with spectral radius at least $cn^{\varepsilon}$ that do not contain such an almost regular subgraph. Our result has a wide range of applications in spectral Tur\'{a}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\geq\xi > \frac{1}{2}$, $ex(n,\mathcal{H}) = O(n^{1+\xi})$ if and only if $spex(n,\mathcal{H}) = O(n^\xi)$. Comment: 9 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|