Cryptography Reference
In-Depth Information
Theorem 3 Let A
1
;:::;A
n
and B
1
;:::;B
n
be two collections of sets satisfy-
ing
=
\
\
A
i
B
i
i2S
i2S
for all proper subsets S of f1;:::;ng. Then
S
i=1
B
i
S
i=1
A
i
1
S
i=1
B
i
2
n1
:
The bound is sharp.
Proof
We prove by induction on n that the conditions
=
\
\
A
i
B
i
i2S
i2S
for all S(f1;:::;ng and the condition
+ k =
[
[
A
i
B
i
i=1
i=1
with k > 0 imply that
k2
n1
:
[
B
i
i=1
For n = 1 this is trivial. Now suppose that the theorem holds for n and
let the sets A
1
;:::;A
n+1
and B
1
;:::;B
n+1
satisfy
=
\
\
A
i
B
i
i2S
i2S
for all S(f1;:::;n + 1g and
+ k =
:
n+
[
n+
[
A
i
B
i
i=1
i=1
The collections A
0
i
= A
i
nA
n+1
and B
0
i
= B
i
nB
n+1
satisfy j
S
i=1
A
0
i
j+ k =
j
S
i=1
B
0
i
j and for every proper subset S(f1;:::;ng we have
=
\
\
\
A
0
i
A
i
A
i
\A
n+1
i2S
i2S
i2S
=
:
\
\
\
B
0
i
=
B
i
B
i
\B
n+1
i2S
i2S
i2S
Search WWH ::
Custom Search