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

Let CLQ=CLQ 1 .Aslongasthereexists v

∈ V − P − M such that the following is

true:

2 ( k

− p − m )

μ CLQ( V , P , M ) (CLQ( v )) ≥

m ) μ CLQ( V , P , M ) (CLQ)

(9.2)

( n − p −

, p by p ∗ = p + 1, and CLQ by CLQ ∗ =CLQ( v ) .Here

replace P by P ∗ = P ∪{ v }

( k − p − m ) μ CLQ( V , P , M ) (CLQ) / ( n − p − m ) is the average of μ CLQ( V , P , M ) (CLQ( v ))

over all v ∈ V − P − M .Thus, CLQ( v ) has measure at least twice the average.

CLQ( V , P ∗ , M ) | | =( k − p − m ) | CLQ( V , P , M ) | / ( n − p − m ) after each iteration

Since

of this loop, the following bound holds:

μ CLQ( V , P ∗ , M ) (CLQ ∗ ) ≥

2 μ CLQ( V , P , M ) (CLQ)

That is, the renormalized measure of the set of cliques after one iteration of the loop is at
least double that of the measure before the iteration.
After exiting from this loop let CLQ t =CLQ ∗

and let P t = P .Since P t contains

p t − p t− 1 more items than P t− 1 , the following inequality holds:

μ CLQ( V , P t , M t ) (CLQ t )

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

≥

2 p t −p t − 1 μ CLQ( V , P t − 1 , M t − 1 ) (CLQ t− 1 ) / 2 ≥ (9.3)

Furthermore, for any vertex v remaining in V

− P the condition expressed in ( 9.2 )is

violated, so that the following holds for v

∈ V − P ,where α = 2 ( k − p t − m t− 1 ) / ( n −

p t − m t− 1 ) :

) <α μ CLQ( V , P t , M t − 1 ) (CLQ t ) (9.4)

CLQ t |

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

3) Let COL t = .Thatis, COL t { c ∈ COL t− 1 | c is 1-1 on P t } is the set of ( k − 1 ) -

1 ) -
colorings we do not increase the number of rounds. In Lemma 9.7.3 we develop a lower
bound on μ COL( V , M t − 1 ) (COL t ) in terms of μ COL( V , M t − 1 ) (COL t− 1 ) .
4) Let M = M t− 1 and m = m t− 1 .LetCOL 0 and COL 1 denote the subsets of COL t
consistent with the values b COL = 0and b COL = 1, respectively. Let COL be the larger
of these two sets. Then μ COL( V , M ) (COL)

colorings in COL t thatassignsuniquecolorstoverticesin P t . By restricting the ( k −

μ COL( V , M ) (COL t ) / 2. ≥

5) The set COL t ( u , v )= { c ∈ COL | c ( u )= c ( v ) } contains those ( k − 1 ) -colorings in

COL for which vertices u and v have the same color.
As long as there exist u , v

∈ V − M such that the following is true:

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

2 μ COL( V , M ) (COL) / ( k

−

1 )

let w be one of u and v that is not in P (they cannot both be in P and have the same color
because each coloring is 1-1 on P ); replace M by M ∗ = M , m by m ∗ = m + 1,

∪{ w }

and COL by COL ∗ =COL t ( u , v ) .
The term μ COL( V , M ) (COL) / ( k − 1 ) is the average of μ COL( V , M ) (COL t ( u , v )) over all

M .Thus, COL ∗ contains ( k

u and v in V − − 1 ) -colorings whose measure is at least

twice the average.