Cross-Intersecting Families of Vectors - Discrete and Computational Geometry and Graphs - page 125

r -intersecting families can be obtained in this way, for certain size vectors. They
considered size vectors p =( k,...,k ) with n

r + 2 coordinates, and noticed
that a Hamming ball of radius 1 in r + 2 coordinates is r -intersecting. Moreover,
for k

≥

r , this family is strictly larger than the trivial r -intersecting family. See
also [ AhK98 ].
On the other hand, as was mentioned before, for k

≤

r +2, Moon [ Mo82 ]
proved that among all r -intersecting families, the trivial ones are maximal.
This leaves open only the case k = r + 1, where the trivial r -intersecting
families and the radius 1 balls in r + 2 coordinates have precisely the same
size. We believe that in this case there are no larger r -intersecting families. For
r = 1, it can be and has been easily verified (and follows, for example, from
our Theorem 1 , which deals with the asymmetric case, when A and B do not
necessarily coincide). Our Theorem 7 settles the problem also for r> 6. The
intermediate cases 2

≥

≤ r ≤ 6 are still open, but they could possibly be handled

by computer search.
Therefore, to characterize maximal size r -intersecting families A or maximal
r -cross-intersecting pairs of families ( A, B )for all size vectors, we cannot restrict
ourselves to fixing r coordinates. We make the following conjecture that can
roughly be considered as a generalization of the Frankl-Furedi conjecture [ FF80 ]
that has been proved by Frankl and Tokushige [ FT99 ]. The generalization is
twofold: we consider r -cross-intersecting pairs rather than r -intersecting families
and we allow arbitrary size vectors not just vectors with all-equal coordinates.

Conjecture 3. n and p is a size vector of length n , then there

exists a maximal pair of r -cross-intersecting families A, B

If 1 ≤ r ≤

ↆ S p ,where A and

B are balls. If we further have p i ≥

3 for all i

∈

[ n ] , then all maximal pairs of

r -cross-intersecting families consist of balls.

Note that the r = 1 special case of Conjecture 3 is established by Theorem 1 .
Some further special cases of the conjecture are settled in Theorem 7 .
It is not hard to narrow down the range of possibilities for maximal r -cross-
intersecting pairs that are formed by two balls, A and B . In fact, the following
simple lemma implies that all such pairs are determined up to isomorphism
by the radii of A and B . Assuming that Conjecture 3 is true, finding max

| A |·

| S p boils down to making numeric

comparisons for pairs of balls obtained by all possible radii. In case p i

B |

for r -cross-intersecting families A, B

ↆ

≥ 3for

all i , the same process also finds all maximal r -cross-intersecting pairs.

Lemma 4. ↆ

S p form a maximal pair of r -cross-intersecting families, then either of them
determines the other. In particular, A and B have the same set of relevant
coordinates. Moreover, if A is a ball of radius l around x 0

≤ r ≤ n and let p =( p 1 ,...,p n ) be a size vector. If A, B

Let 1

∈ S p in a set of

coordinates T ↆ [ n ] , then | T |≥ l + r , B is a ball of radius | T |− l − r around x 0

in the same set of the coordinates, and we have p i ≤ p j for i ∈ T and j ∈ [ n ] \ T .

As we have indicated above, we have been unable to prove Conjecture 3 in its
full generality, but we were able to verify it in several interesting special cases.