Information Technology Reference
In-Depth Information
Cases 2, 3, and 5 are not possible, because either
i
or
j
would not be relevant
for
B
.
In case 1, we have
B
=
U
0
, and thus
A
=
U
2
. In this case,
A
and
B
are
balls, but the radius of
A
is 2. This is impossible, as
U
1
is
r
-intersecting and
|
2
>
always holds, so (
A, B
) is not maximal.
It remains to deal with case 4. Here supp(
A
) consists of the sets of size at
most 1 and the two-element set
U
1
|
|
U
0
|·|
U
2
|
{
i, j
}
. Define
C
=
{
x
∈
S
p
:
x
k
= 1 for all
k
∈
[
n
]
\{
i, j
}}
.
Note that
, because each vector in
S
p
appears in the
same number of sets on both sides. Thus, we have either
|
A
|
+
|
B
|
=
|
U
1
|
+
|
C
|
|
A
|
+
|
B
|≤
2
|
U
1
|
or
2
|
A
|
+
|
B
|≤
2
|
C
|
. Since
|
A
|
>
|
B
|
, the above inequalities imply
|
A
|·|
B
|
<
|
U
1
|
2
. This contradicts the maximality of the pair (
A, B
), because
both
U
1
and
C
are
r
-intersecting. The contradiction completes the proof of
Theorem
8
.
or
|
A
|·|
B
|
<
|
C
|
Let us remark here that the extension of Theorem
8
to somewhat larger values of
relevant coordinates (in other words, verifying Conjecture
3
for the case of, say
r
+ 4 relevant coordinates) yield a similar case analysis as we saw above for
r
+2
relevant coordinates, but with much more cases corresponding to containment
maximal pairs of set systems (
U, V
) with
|
u
∪
v
|
bounded for
u
∈
U
and
v
∈
V
.
This seems to be doable, but the number of cases to considers grow fast.
Now we can prove our main theorem, verifying Conjecture
3
in several special
cases.
Proof of Theorem 7.
The statement about the case
p
1
>r
+ 1 readily follows
from Lemma
2
, as in this case the condition
r
2
p
r
+1
1
p
i
≤
+
1
i
=1
holds.
To prove the other two statements in the theorem, we assume that
A
and
B
form a maximal
r
-cross-intersecting pair. We also assume without loss of
generality that all coordinates are relevant for both families (simply drop the
irrelevant coordinates).
By Theorem
6
,wehave
i
=1
p
i
≥
i
=1
(
p
i
−
1)
1
−
2
/p
i
, and thus
r
n
p
i
1)
1
−
2
/p
i
.
1)
1
−
2
/p
i
≥
(
p
i
−
(
p
i
−
i
=1
i
=
r
+1
1)
1
−
2
/x
is decreasing for
x
1)
1
−
2
/x
is
Here the function
x/
(
x
−
≥
3, while (
x
−
increasing, and we have
p
i
≥
p
1
≥
3. Therefore, we also have
r
n
p
1
1)
1
−
2
/p
1
,
1)
1
−
2
/p
1
≥
(
p
1
−
(
p
1
−
i
=1
i
=
r
+1
Search WWH ::
Custom Search