Randomly finding independent sets in locally sparse graphs

For graph G with vertex set V and $$u\in V$$ u ∈ V , we write $$d_u$$ d u to be the degree of u. For $$\emptyset \ne S\subseteq V$$ ∅ ≠ S ⊆ V , the independence ratio of S is defined as $$\rho (S)=\min \{\frac{\alpha (T)}{|T|}:\;\emptyset \ne T\subseteq S\}$$ ρ ( S ) = min { α ( T ) | T | : ∅ ≠ T ⊆ S } , where $$\alpha (T)$$ α ( T ) is the independence number of the graph induced by T in G. Let $$N_i(u)=\{w\in V:\;dist(u,w)=i\}$$ N i ( u ) = { w ∈ V : d i s t ( u , w ) = i } . We shall show that if $$\rho _0>0$$ ρ 0 > 0 and a graph G has $$\rho (N_i(u))\ge \rho _0$$ ρ ( N i ( u ) ) ≥ ρ 0 for each $$u\in V$$ u ∈ V and $$i\le k$$ i ≤ k , then its independence number is at least $$a\left( \sum _{u}d_u^{1/(k-1)}\right) ^{(k-1)/k}$$ a ∑ u d u 1 / ( k - 1 ) ( k - 1 ) / k , where $$a=a(k,\rho _0)>0$$ a = a ( k , ρ 0 ) > 0 is independent of G. This result generalizes some former results for graphs with forbidden odd cycles.