  We give the first nonconstant lower bounds for the approximability of the
Independent Set Problem on the Power Law Graphs. These bounds are of the form
$n^{\epsilon}$ in the case when the power law exponent satisfies $\beta <1$. In
the case when $\beta =1$, the lower bound is of the form $\log (n)^{\epsilon}$.
The embedding technique used in the proof could also be of independent
interest.
