Information Technology Reference
In-Depth Information
With an involved case analysis, it may be possible to extend Theorem
8
to
pairs with more relevant coordinates. Any such an improvement carries over to
Theorem
7
.
All of our results remain meaningful in the symmetric case where
A
=
B
.For
instance, in this case, Theorem
1
(also proved by Borg [
Bo14
]) states that every
intersecting family
A
/k
members, where
k
= min
i
p
i
.
In case
k>
2, equality can be achieved only by fixing some coordinate
i
with
p
i
=
k
. Note that in the case
A
=
B
(i.e.,
r
-intersecting families) the exact
maximum size is known for size vectors (
q,...,q
), [
FT99
].
ↆ
S
p
has at most
|
S
p
|
2 Proof of Theorem
1
The aim of this section is to establish Theorem
1
. First, we verify Lemma
4
and another technical lemma (see Lemma
9
below), which generalizes the corre-
sponding result in [
Mo82
]. Our proof is slightly simpler. Lemma
9
will enable us
to deduce Lemma
2
, the main ingredient of the proof of Theorem
1
,presentedat
the end of the section.
Proof of Lemma 4.
The first statement is self-evident: if
A, B
ↆ
S
p
form a max-
imal pair of
r
-cross-intersecting families, then
B
=
{
x
∈
S
p
:
xr
-intersects
y
for all
y
∈
A
}
.
If a coordinate is irrelevant for
A
, then it is also irrelevant for
B
defined by
this formula. Therefore, by symmetry,
A
and
B
have the same set of relevant
coordinates.
If
A
is the Hamming ball around
x
0
of radius
l
in coordinates
T
, then we
have
B
=
∅
if
|
T
|
<l
+
r
, which is not possible for a maximal cross-intersecting
family. If
|
T
|≥
l
+
r
, we obtain the ball claimed in the lemma. For every
i
∈
T
,
T
, consider the set
T
=(
T
and the Hamming balls
A
j
∈
[
n
]
\
\{
i
}
)
∪{
j
}
and
B
of radii
l
and
r
around
x
0
in the coordinates
T
. These balls form an
r
-cross-intersecting pair and in case
p
i
>p
j
,wehave
|
T
|−
l
−
A
|
B
|
|
>
|
A
|
and
|
>
|
B
|
,
contradicting the maximality of the pair (
A, B
).
The following lemma will also be used in the proof of Theorem
5
,presentedin
the next section.
Lemma 9.
Let
1
≤
r
≤
n
,let
p
=(
p
1
,...,p
n
)
be a size vector, and let
A, B
ↆ
S
p
form a maximal pair of
r
-cross-intersecting families.
If
i
∈
[
n
]
is a relevant coordinate for
A
or
B
, then there exists a value
l
∈
[
p
i
]
such that
|{
x
∈
A
:
x
i
=
l
}| ≤ |
A
|
/p
i
,
|{
y
∈
B
:
y
i
=
l
}| ≤ |
B
|
/p
i
.
Search WWH ::
Custom Search