Information Technology Reference
In-Depth Information
This family is
r
-intersecting. Thus, by the maximality of the pair (
A, B
), we
have
2
=
2
n
|
A
|·|
B
|≥|
C
|
p
i
.
(4)
i
=
r
+1
Comparing this with our upper bounds on
|
A
|
and
|
B
|
, we obtain the inequality
claimed in the theorem.
To prove the required bound on the number of relevant coordinates
i
with
p
i
= 2, we assume that the coordinates are ordered, that is
p
1
≤
p
2
≤ ··· ≤
p
n
. Applying the above estimate on
i∈
[
r
]
p
i
and using (
p
i
−
1)
1
−
2
/p
i
>p
1
/
5
i
whenever
p
i
≥
3, the theorem follows.
4 Monotone Families: Proofs of Theorems
8
and
7
Given a vector
x
∈
S
p
, the set supp(
x
)=
{
i
∈
[
n
]:
x
i
>
1
}
is called the
support
of
x
. A family
A
ↆ
S
p
is said to be
monotone
, if for any
x
∈
A
and
y
∈
S
p
satisfying supp(
y
)
ↆ
supp(
x
), we have
y
∈
A
.
For a family
A
ↆ
S
p
, let us define its
support
as supp(
A
)=
{
supp(
x
):
x
∈
A
. For a monotone family
A
, its support is clearly subset-closed and it uniquely
determines
A
,as
A
=
}
.
The next result shows that if we want to prove Conjecture
3
, it is sucient
to prove it for monotone families. This will enable us to establish Theorems
8
and
7
, that is, to verify the conjecture for maximal
r
-cross-intersecting pairs
with a limited number of relevant coordinates. Note that similar reduction to
monotone families appears also in [
FF80
].
{
x
∈
S
p
: supp(
x
)
∈
supp(
A
)
}
Lemma 10.
n
and let
p
be a size vector of length
n
.
There exists a maximal pair of
r
-cross-intersecting families
A, B
Let
1
≤
r
≤
ↆ
S
p
such
that both
A
and
B
are monotone.
If
p
i
S
p
are maximal
r
-cross-intersecting
families that are
not
balls, then there exists a pair of maximal
r
-cross-intersecting
families that consists of monotone families that are not balls and have no more
relevant coordinates than
A
or
B
.
≥
3
for all
i
∈
[
n
]
and
A, B
ↆ
Proof.
Consider the following
shift operations
. For any
i
∈
[
n
]and
j
∈
[
p
i
]
\{
1
}
,
for any family
A
ↆ
S
p
and any element
x
∈
A
, we define
φ
i
(
x
)=(
x
1
,...,x
i−
1
,
1
,x
i
+1
,...,x
n
)
,
φ
i,j
(
x, A
)=
φ
i
(
x
) f
x
i
=
j
and
φ
i
(
x
)
/
∈
A
x
otherwise,
φ
i,j
(
A
)=
{
φ
i,j
(
x, A
):
x
∈
A
}
.
|
φ
i,j
(
A
)
|
|
A
|
for any family
A
ↆ
S
p
. We claim that for any pair
Clearly, we have
=
of
r
-cross-intersecting families
A, B
ↆ
S
p
, the families
φ
i,j
(
A
)and
φ
i,j
(
B
)are
Search WWH ::
Custom Search