Originator(s): Noga Alon, Michael Krivelevich, and Benny Sudakov (presented by Mohit Kumbhat- REGS 2008)
Definitions: A graph G is c-nearly regular if Δ(G)≤c&delta(G);. Let f(n,c) denote the maximum integer t so that every graph on n vertices contains a c-nearly regular induced subgraph with at least t vertices. The density of a graph G, written ρ(G), is defined by ρ(G)=|E(G)|/(2|V(G)|).
Background: The problem of estimating f(n,1) (guaranteeing large regular induced subgraphs) was posed long ago by Erdős, Fajtlowicz, and Staton (see [E]).
Conjecture 1 (Erdős-Fajtlowicz-Staton): f(n,1)/ln n →∞ as n→∞
Comments:
Alon, Krivelevich, and Sudakov [AKS] showed the following:
(i) If c≥2.1, then
n(1-O(1/c))≤f(n,c)≤O(cn/log n).
(ii) If c=1+ε with ε>0, then
f(n,c)≥nΩ(ε2/ln(1/ε)).
(iii)
Ω(lnn)≤f(n,1)≤O(n1/2ln1/4n).
The upper bound in (i) is by a construction with n=(s+1)ss
and
G=∪0≤i≤s2s-iK2i.
The lower bound in (iii) comes from Ramsey's Theorem, implying that every
n-vertex graph has a clique or an independent set of size at least
ln n. The upper bound in (iii) is a slight improvement of an earlier
result of Bollobás reported in [CG]. It uses an unusual random graph
model where the probability of the edge vivj is
pipj, with pi=¼+i/(2n).
Question 2: What are the best asymptotic bounds on f(n,c) for fixed c?
Question 3:(West) How can the bounds on f(n,1) be improved when restricted to n-vertex graphs with a certain density ρ or a certain number of edges (such as √n)?
Comments: Note that although a random graph and its complement are equality likely, they do not have the same nearness to regularity ratio of maximum to minimum degree. [AKS] proves that if G has n vertices and density ρ, then G has a (1+ε)-nearly regular induce subgraph with at least .5(&epsilon/6)(144/&epsilon²)ln(1/ρ)n vertices.
[AKS] also considers a similar problem for not necessarily induced subgraphs. They prove that if m>n and c>2 and d=2m/n, then G contains a c-nearly regular subgraph with at least d²/c12 edges.
References:
[AKS] Alon, N; Krivelevich, M; Sudakov, B; Large nearly regular induced
subgraphs; preprint.
[CG] Chung, F and Graham, R, Erdős on Graphs: His legacy of Unsolved
Problems, A.K.Peters Ltd., Wellesly, MA, 1998.
[E] Erdős, P, On some of my favourite problems in various branches of
combinatorics, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and
Complexity, 69-79, Ann Discrete Math, 51, 1992.
[FS] Fajtlowicz, S; McColgan, T.; Reid, T.; Staton, W.;
Ramsey numbers for induced regular subgraphs,
Ars Combin. 39(1995), 149-154.