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