Information Technology Reference
In-Depth Information
|
COL(
V
,
M
∗
)
|
|
COL(
V
,
M
)
|
/
(
k
−
Since
=
1
)
after each iteration of this loop, the
following holds:
μ
COL(
V
,
M
∗
)
(COL
∗
)
2
μ
COL(
V
,
M
)
(COL)
That is, the renormalized measure of the set of
(
k
≥
1
)
-colorings after each loop iteration
is at least double that of the measure before the iteration.
After exiting from this loop, let
M
t
=
M
.Since
M
t
contains
m
t
−
−
m
t−
1
more items than
M
t−
1
, the following inequality holds:
μ
COL(
V
,
M
t
−
1
)
(COL
∗
)
2
m
t
−m
t
−
1
μ
COL(
V
,
M
t
−
1
)
(COL)
≥
2
m
t
−m
t
−
1
μ
COL(
V
,
M
t
−
1
)
(COL
t
)
/
2
≥
(9.5)
6) Let
COL
t
=COL
∗
,
M
t
=
M
,and
CLQ
t
=
CLQ
t
|
.Thus,
CLQ
t
does not contain any cliques with vertices in
M
t
. In Lemma
9.7.4
we develop a lower
bound on
μ
CLQ(
V
,
P
t
,
M
t
−
1
)
(CLQ
t
)
in terms of
μ
CLQ(
V
,
P
t
,
M
t
−
1
)
(CLQ
t
)
.
{
q
∈
M
t
∩
q
=
∅}
PERFORMANCE OF THE ADVERSARIAL STRATEGY
We establish three lemmas and then derive
the lower bound on the number of rounds of the communication game.
LEMMA
9.7.3
After step
3
of the adversarial selection the following inequality holds:
1
μ
COL(
V
,
M
t
−
1
)
(COL
t−
1
)
(
p
t
+
1
)
2
k
μ
COL(
V
,
M
t
−
1
)
(COL
t
)
≥
−
−
1
Proof
Recall the definition of
COL
t
(
u
,
v
)=
. Consider the
results of step 3 of the
t
th round in the adversary selection process. Because of the choices
made in step 5 in the
(
t
{
c
∈
COL
|
c
(
u
)=
c
(
v
)
}
−
1
)
st round and the choice of COL
0
, the following inequality
holds for all
t>
0and
u
,
v
∈
V
−
M
t−
1
when
u
=
v
:
μ
COL(
V
,
M
t
−
1
)
(COL
t
(
u
,
v
))
<
2
μ
COL(
V
,
M
t
−
1
)
(COL
t−
1
)
/
(
k
−
1
)
Because
M
t
=
M
t−
1
at step 3 of the
t
th round and
P
t
⊆
V
−
M
t
, the same bound applies
for
u
and
v
in
P
t
.
The set
COL
t−
1
is reduced to
COL
t
=
{
c
∈
|
c
is 1 to 1 on
P
t
}
COL
t−
1
by discard-
ing
(
k
1
)
-colorings for which
u
and
v
are in
P
t
and have the same color. From the above
facts the following inequalities hold (here instances of the measure
μ
carry the subscript
COL(
V
,
M
t−
1
)
):
μ
(COL
t
)=
μ
(
−
{
c
∈
COL
t−
1
|
c
is 1 to 1 on
P
t
}
)
⎛
⎞
⎝
⎠
=
μ
(COL
t−
1
)
−
μ
COL
t
(
u
,
v
)
u
,
v∈P
t
,
u
=
v
≥
μ
(COL
t−
1
)
−
COL
t
(
u
,
v
)
u
,
v∈P
t
,
u
=
v
>
1
p
t
2
μ
(COL
t−
1
)
2
−
k
−
1
>
1
μ
(COL
t−
1
)
(
p
t
+
1
)
2
k
−
−
1
Search WWH ::
Custom Search