Information Technology Reference
In-Depth Information
We solve the resulting inequality
p
i
≤
c
(1 + (
p
i
−
1)
/c
)
2
for
c>
1 and conclude
1)
2
. This inequality, together with Eqs. (
1
) and (
2
), completes the
proof of Lemma
9
.
that
c
≥
(
p
i
−
Proof of Lemma 2.
We proceed by induction on
n
.
Let
A
and
B
form a maximal
r
-cross-intersecting pair. It is sucient to show
that they have only
r
relevant coordinates. Let us suppose that the set
T
of
their relevant coordinates satisfies
>r
, and choose a subset
T
|
T
|
ↆ
T
with
T
|
|
=
r
+ 1. By Lemma
9
, for every
i
∈
T
there exists
l
i
∈
[
p
i
] such that the
family
X
i
=
{
x
∈
B
:
x
i
=
l
i
}
has cardinality
|
X
i
|≤|
B
|
/p
i
.
If we assume that
r
2
p
r
+1
+
1
p
i
<
1
i
=1
holds (with strict inequality), then this bound of
|
X
i
|
would suce. In order to
be able to deal with the case
r
2
p
r
+1
+
1
p
i
=1
,
i
=1
we show that
/p
i
is not possible. Considering the proof of Lemma
9
,
equality here would mean that the families
A
l
and
B
l
(obtained by dropping the
i
th coordinate from the vectors in the sets
|
X
i
|
=
|
B
|
{
x
∈
A
:
x
i
=
l
}
and
{
y
∈
B
:
y
i
=
l
, respectively) satisfy the following condition: both (
A
l
i
,B
m
) and (
A
m
,B
l
i
)
should be maximal
r
-cross-intersecting pairs for all
m
}
=
l
i
. By the induction
hypothesis, this would imply that
A
l
i
=
B
m
and
A
m
=
B
l
i
, contradicting that
|
A
m
|
<
|
A
l
i
|
and
|
B
m
|
<
|
B
l
i
|
(see (
1
), in view of
c>
1). Therefore, we have
|
X
i
|
/p
i
.
Let
C
=
<
|
B
|
be the
r
-intersecting family
obtained by fixing
r
coordinates in
S
p
. In the family
D
=
B
{
x
∈
S
p
x
i
= 1 for all
i
∈
[
r
]
}
:
(
i∈T
X
i
), the
\
coordinates in
T
are fixed. Thus, we have
n
|
D
|≤
p
i
≤
p
i
=
|
C
|
/p
r
+1
.
i
=
r
+2
i∈
[
n
]
\T
On the other hand, we have
i∈T
|
r
+1
|
D
|
|
B
|−
X
i
|
>
|
B
|
−
1
/p
i
)
≥|
B
|
−
1
/p
i
)
.
=
(1
(1
i∈T
i
=1
Comparing the last two inequalities, we obtain
|
C
|
i
=1
1
/p
i
)
.
By our assumption on
p
, the denominator is at least 1, so that we have
|
B
|
<
−
r
+1
p
r
+1
(1
|
B
|
<
|
C
|
.
2
contradicting the
maximality of the pair (
A, B
). This completes the proof of Lemma
2
.
By symmetry, we also have
|
A
|
<
|
C
|
.Thus,
|
A
|·|
B
|
<
|
C
|
Search WWH ::
Custom Search