Information Technology Reference
In-Depth Information
are said to be
B
-critical
. By the definition of
φ
i,j
, the family
A
differs from
A
by
including some
A
-critical vectors
x
and losing the corresponding vectors
φ
i
(
x
).
Symmetrically,
B
B
consists of some
B
-critical vectors
y
and
B
\
B
consists of
the corresponding vectors
φ
i
(
y
). Let us consider the bipartite graph
G
whose
vertices on one side are the
A
-critical vectors
x
, the vertices on the other side
are the
B
-critical vectors
y
(considered as disjoint families, even if
l
=
m
), and
x
is adjacent to
y
if and only if
\
=
r
.If
x
and
y
are adjacent,
then neither the pair (
x, φ
i
(
y
)), nor the pair (
φ
i
(
x
)
,y
)is
r
-intersecting. As
A
and
B
are
r
-cross-intersecting, for any pair of adjacent vertices
x
and
y
of
G
,we
have
x
|{
k
∈
[
n
]:
x
k
=
y
k
}|
B
.
The crucial observation is that the graph
G
is connected. Note that this is
not the case if
p
k
= 2 for some index
k/
∈
A
if and only if
y
∈
T
, since all
A
-critical vectors
x
in a
connected component of
G
would have the same value
x
k
. However, we assumed
that
p
k
>
2for
l
∈
[
n
]. In this case, the
A
-critical vectors
x
and
x
have a
common
B
-critical neighbor (and, therefore, their distance in
G
is 2) if and only
if the symmetric difference of the
l
element sets
∈
{
k
∈
T
\{
i
}
:
x
k
=(
x
0
)
k
}
and
:
x
k
{
2 elements. We assumed that
r>
1,
so this means that all
A
-critical vectors are indeed in the same component of
the graph
G
. Therefore, either all
A
-critical vectors belong to
A
or none of them
does. In the latter case, we have
A
=
A
. In the former case,
A
is the Hamming
ball of radius
l
in coordinates
T
around the vector
x
0
, where
x
0
agrees with
x
0
in all coordinates but in (
x
0
)
i
=
j
. In either case,
A
is a ball as required.
k
∈
T
\{
i
}
=(
x
0
)
k
}
have at most 2
r
−
Proof of Theorem 8.
By Lemma
10
, it is enough to restrict our attention to
monotone families
A
and
B
. We may also assume that all coordinates are relevant
(simply drop the irrelevant coordinates), and thus we have
n
r
+2.
We denote by
U
l
the Hamming ball of radius
l
around the all-1 vector in
the entire set of coordinates [
n
]. Notice that the monotone families
A
and
B
are
r
-cross-intersecting if and only if for
a
≤
∈
supp(
A
)and
b
∈
supp(
B
)wehave
|
r
, separately.
If
n
=
r
, both families
A
and
B
must coincide with the singleton
U
0
.
If
n
=
r
+ 1, it is still true that either
A
or
B
is
U
0
. Otherwise, both supp(
A
)
and supp(
B
) have to contain at least one non-empty set, but the union of these
sets has size at most
n
a
∪
b
|≤
n
−
r
. We consider all possible values of
n
−
−
r
=1,sowehavesupp(
A
) = supp(
B
)=
{∅
,
{
i
}}
for some
i
[
n
]. But this contradicts our assumption that the coordinate
i
is
relevant for
A
.
If
n
=
r
+ 2, we are done if
A
=
B
=
U
1
. Otherwise, we must have a two-
element set either in supp(
A
)orinsupp(
B
). Let us assume that a two-element
set
∈
.
This leaves five possibilities for a non-empty monotone family
B
, as supp(
B
)
must be one of the following set systems:
{
i, j
}
belongs to supp(
A
). Then each set
b
∈
supp(
B
) must satisfy
b
ↆ{
i, j
}
{∅}
1.
,
{∅
,
{
i
}}
2.
,
3.
{∅
,
{
j
}}
,
4.
{∅
,
{
i
}
,
{
j
}}
,and
5.
{∅
,
{
i
}
,
{
j
}
,
{
i, j
}}
.
Search WWH ::
Custom Search