Theory of Computational Complexity, 2nd Edition

Lemma 11.14

For every and c ≥ 1, there exist and such that, for integers , if , then for every k satisfying , we have

The second lemma is often called the Second Moment Method for the estimation of for a nonnegative random variable X.

Lemma 11.15

If X is a nonnegative random variable, then

Now, we are ready to show that the power graph G^t satisfies our needs.

Lemma 11.16

(Powering) Let and be arbitrary constants. There exists a constant such that for every and for ...