Information Technology Reference
In-Depth Information
S
p
if, whenever
two elements of
S
p
differ only in coordinate
i
and
A
contains one of them, it also
contains the other. Otherwise, we say that
i
is
relevant
for
A
.
Note that no coordinate
i
with
p
i
= 1 can be relevant for any family. Each
such coordinate forces an intersection between every pair of vectors. So, if we
delete it, every
r
-cross-intersecting pair becomes (
r
We say that a coordinate
i
∈
[
n
]is
irrelevant
for a set
A
ↆ
1)-cross-intersecting. There-
fore, from now on we will always assume that we have
p
i
≥
−
2 for every
i
.
We call a sequence of integers
p
=(
p
1
,...,p
n
)a
size vector
if
p
i
≥
2for
all
i
.The
length
of
p
is
n
. We say that an
r
-cross-intersecting pair
A, B
ↆ
S
p
is
maximal
if it maximizes the value
.
Using this notation and terminology, Theorem
1
can be rephrased as follows.
|
A
|·|
B
|
Theorem 1'.
Let
p
=(
p
1
,...,p
n
)
be a sequence of positive integers with
k
=
min
i
p
i
>
2
.
For any maximal pair of cross-intersecting families,
A, B
S
p
, we have
A
=
B
, and there is a single coordinate which is relevant for
A
. The relevant
coordinate
i
must satisfy
p
i
=
k
.
ↆ
See Sect.
5
for a complete characterization of maximal cross-intersecting pairs
in the
k
= 2 case. Here we mention that only the coordinates with
p
i
= 2 can
be relevant for them, but for certain pairs,
all
such coordinates are relevant
simultaneously. For example, let
n
be odd,
p
=(2
,...,
2), and let
A
=
B
consist
of all vectors in
S
p
which have at most
n/
2
coordinates that are 1. This makes
(
A, B
) a maximal cross-intersecting pair.
Let
T
ↆ
[
n
] be a subset of the coordinates, let
x
0
∈
S
p
be an arbitrary vector,
and let
k
be an integer satisfying 0
.The
Hamming ball
of radius
k
around
x
0
in the coordinates
T
is defined as the family
≤
k
≤|
T
|
B
k
=
{
x
∈
S
p
:
|{
i
∈
T
:
x
i
=(
x
0
)
i
}| ≤
k
}
.
Note that the pair (
B
k
,B
l
)is(
l
)-cross-intersecting. We use the word
bal l
to refer to any Hamming ball without specifying its center, radius or its
set of coordinates. A Hamming ball of radius 0 in coordinates
T
is said to be
obtained by
fixing
the coordinates in
T
.
For the proof of Theorem
1
, we need the following statement, which will be
established by induction on
n
, using the idea in [
Mo82
].
|
T
|−
k
−
Lemma 2.
Let
1
≤
r<n
,let
p
=(
p
1
,...,p
n
)
be a size vector satisfying
3
≤
p
1
≤
p
2
≤ ··· ≤
p
n
and let
A, B
ↆ
S
p
form a pair of
r
-cross-intersecting
families. If
r
2
p
r
+1
+
1
p
i
≤
1
,
i
=1
|≤
i
=
r
+1
p
i
. In case of equality, we have
A
=
B
and this family
can be obtained by fixing
r
coordinates in
S
p
.
then
|
A
|·|
B
By fixing any
r
coordinates, we obtain a “trivial”
r
-intersecting family
A
=
B
ↆ
S
p
. As was observed by Frankl and Furedi [
FF80
], not all maximal size
Search WWH ::
Custom Search