Large nearly regular induced subgraphs
| dc.creator | Alon, Noga | |
| dc.creator | Krivelevich, Michael | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-10-10 | |
| dc.date | 2008-02-25 | |
| dc.date.accessioned | 2026-07-07T09:22:42Z | |
| dc.date.available | 2026-07-07T09:22:42Z | |
| dc.description | For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least f(n,1) vertices. The problem of estimating $(n,1) was posed long time ago by Erdos, Fajtlowicz and Staton. In this note we obtain the following upper and lower bounds for the asymptotic behavior of f(n,c): (i) For fixed c>2.1, n^{1-O(1/c)} \leq f(n,c) \leq O(cn/\log n). (ii) For fixed c=1+εwith epsilon>0 sufficiently small, f(n,c) \geq n^{Ω(ε^2/ \ln (1/ε))}. (iii) Ω(\ln n) \leq f(n,1) \leq O(n^{1/2} \ln^{3/4} n). An analogous problem for not necessarily induced subgraphs is briefly considered as well. | |
| dc.identifier | https://arxiv.org/abs/0710.2106 | |
| dc.identifier | http://arxiv.org/abs/0710.2106 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155471 | |
| dc.subject | Combinatorics | |
| dc.title | Large nearly regular induced subgraphs | |
| dc.type | text |