Circuit Complexity - Models of Computation: Exploring the Power of Computing - page 446

From this the conclusion follows.
LEMMA 9.7.4 After step 6 of the adversarial selection the following inequality holds:

μ CLQ( V , P t , M t − 1 ) (CLQ t )
Proof As stated in ( 9.4 ), after step 2 of the t th round of the adversary selection process we
have for all v

1

2 km t
n

μ CLQ( V , P t , M t − 1 ) (CLQ t ) ≥ −

∈ V − P t − M t− 1 the following inequality:

) < 2 ( k

− p t − m t− 1 )

CLQ t |

m t− 1 ) μ CLQ( V , P t , M t − 1 ) (CLQ t )

μ CLQ( V , P t , M t − 1 ) ( { q ∈ v ∈ q }

( n − p t −

Since M t ⊆ V − P t , this bound applies to v ∈ M t . In the rest of this proof all instances of

μ carry the subscript CLQ( V , P t , M t− 1 ) .
Since CLQ t = CLQ t |

{ q ∈ M t ∩ q = ∅} , after step 6 the following inequalities hold:

μ (CLQ t )= μ ( { c ∈ CLQ t | M t ∩ q = ∅} )

μ = μ (CLQ t ) CLQ t | −

v∈M t {

c ∈ v ∈ q }

1 μ (CLQ t )

2 ( k

− p t − m t− 1 ) m t

≥ −

( n − p t − m t− 1 )

1 μ (CLQ t )

2 km t
n

≥ −

From this the conclusion follows.

The third lemma sets the stage for the principal result of this section.
LEMMA 9.7.5 Let k ≥ 2 and t ≤ √ k/ 4 and t ≤ n/ ( 8 k ) . Then the following inequalities hold:
μ CLQ( V , P t , M t − 1 ) (CLQ t ) 2 p t − 2 t ≥

2 m t − 2 t
Proof The inequalities hold for t = 0because μ CLQ( V , P 0 ) (CLQ 0 )= μ COL( V , M 0 ) (COL 0 )=
1. We assume as inductive hypothesis that the inequalities hold for the first t

μ COL( V , M t ) (COL t ) ≥

−

1rounds

and show they hold for the t th round as well.
Using the inductive hypothesis and ( 9.3 ), we have
μ CLQ( V , P t , M t − 1 ) (CLQ t )

2 p t −p t − 1 μ CLQ( V , P t − 1 , M t − 1 ) (CLQ t− 1 ) / 2 2 p t − 2 t + (9.6)

≥ ≥

Since μ CLQ( V , P t ) (CL Q t )

≤

1, we conclude that p t ≤ 2 t

−

1. Using this result, the

≤ √ k/ 4, Lemma 9.7.3 , and the inductive hypothesis, we have

assumption that t

1 μ COL( V , M t − 1 ) (COL t− 1 )

4 t 2

μ COL( V , M t − 1 ) (COL t ) ≥ −

k −

1

1 μ COL( V , M t − 1 ) (COL t− 1 )

k

≥ −

4 ( k

−

1 )

1
2 μ COL( V , M t − 1 ) (COL t− 1 )

≥

2 m t − 1 − 2 t + 1 ≥