Information Technology Reference
In-Depth Information
We execute a series of rounds. During each round each player provides one bit of infor-
mation to the other. This information has the effect of reducing the uncertainty of the color
player about the possible
k
-cliques held by the clique player and of reducing the uncertainty of
the clique player about the possible
(
k
1
)
-colorings held by the color player. The adversary
makes the uncertainty large after each round so that the number of rounds needed will be large
and a structure of the sets of cliques and colorings that can be analyzed will be maintained.
The game ends when both players have found a monochromatic edge that is in a clique.
Let
P
t
⊆
−
V
denote the vertices that after the
t
th round are present in every
k
-clique and missing from every
k
-clique, respectively. (Let
p
t
=
V
and
M
t
⊆
|
P
t
|
and
m
t
=
|
M
t
|
.) Since
vertices in
M
t
are not in any cliques after the
t
th round, as we shall see, each such vertex can
be assigned the same color as a “friend” after all vertices not in
M
t
have been colored. Also,
after the
t
th round the vertices in a
k
-clique consist of vertices in
V
−
M
t
of which those in
P
t
are the same for all such cliques.
Let CLQ
(
V
,
P
t
,
M
t
)
denote the set of
k
-cliques containing
P
t
but no vertex in
M
t
.Let
COL
(
V
,
M
t
)
denote the
(
k
−
1
)
-colorings of vertices not in
M
t
after the
t
th round. Then
=
n−p
t
−m
t
k−p
t
−m
t
and
m
t
)
k−
1
|
CLQ
(
V
,
P
t
,
M
t
)
|
|
COL
(
V
,
M
t
)
|
=(
n
−
are the maximum
numbers of
k
-cliques and
(
k
1
)
-colorings that are possible after the
t
th round. Let CLQ
t
and COL
t
denote the actual number of cliques and colorings that are consistent with the
information exchanged between players after the
t
th round.
Given two sets
A
and
B
,
A
−
⊆
B
,weintroduceameasure
μ
B
(
A
)=
|
A
|
/
|
B
|
used in
deriving our lower bound. For an element
x
A
,
μ
B
(
A
)
is a rough measure of the amount
of information that can be deduced about
x
. The smaller the value of
μ
B
(
A
)
,themore
information we have about
x
. This measure is specialized to cliques and colorings after the
t
th
round:
∈
μ
CLQ(
V
,
P
t
,
M
t
)
(CLQ
t
)=
|
CLQ
t
|
/
|
CLQ(
V
,
P
t
,
M
t
)
|
μ
COL(
V
,
M
t
)
(COL
t
)=
|
COL
t
|
/
|
COL(
V
,
M
t
)
|
Since the color player does not know the identity of vertices in
P
t
until after the
t
th
round, its information about the clique held by the other player is measured by
p
t
and
μ
CLQ(
V
,
P
t
,
M
t
)
(CLQ
t
)
. Since the clique player only knows the color of vertices
M
t
that
are missing in all cliques after the
t
th round, its information about a
(
k
−
1
)
-coloring by the
color player is measured by
m
t
and
μ
COL(
V
,
M
t
)
(COL
t
)
.
The number of rounds,
T
,islargeiffor
t
=
T
no edge present in all remaining cliques
CLQ
t
that is monochromatic in all remaining colorings COL
t
. We show that an adversary
can choose the sets CLQ
t
and COL
t
at each round so that many rounds are needed.
SELECTION OF THE SETS CLQ
T
AND COL
T
BY THE ADVERSARY:
Let the value of the bits sent by
the clique and color players be
b
CLQ
and
b
COL
, respectively. At the
t
th round the following
algorithm is used to choose CLQ
t
and COL
t
:
1) Let
P
=
P
t−
1
,
p
=
p
t
,
M
=
M
t−
1
and
m
=
m
t−
1
.LetCLQ
1
be the larger of the
two subsets of CLQ
t−
1
consistent with the values
b
CLQ
=
0and
b
CLQ
=
1. Thus,
μ
CLQ(
V
,
P
,
M
)
(CLQ
1
)
≥
μ
CLQ(
V
,
P
,
M
)
(CLQ
t−
1
)
/
2.
2) Let CLQ be a collection of
k
-cliques. Then the set of cliques
q
in CLQ containing the
vertex
v
is denoted
CLQ(
v
)=
{
q
∈
CLQ
|
v
∈
q
}
.
Search WWH ::
Custom Search