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

We will refer to the elements of S p as vectors .The Hamming distance between
the vectors x, y

∈ S p is |{ i ∈ [ n ]: x i = y i }| and is denoted by d ( x, y ). Let

r ≥ 1 be an integer. Two vectors x, y ∈ S p are said to be r -intersecting if

d ( x, y ) r . (This term originates in the observation that if we represent

a vector x =( x 1 ,...,x n )

≤ n −

∈ S p by the set { ( i, x i ): i ∈ [ n ] } , then x and

y S p are r -intersecting if and only if the sets representing them have at least

r common elements.) Two families A, B

∈

ↆ S p are r -cross-intersecting ,ifevery

pair x B is r -intersecting. If ( A, A )isan r -cross-intersecting pair, we

say A is r -intersecting . We simply say intersecting or cross-intersecting to mean
1-intersecting or 1-cross-intersecting, respectively.
The investigation of the maximum value for

∈ A , y ∈

| A |·| B | for cross-intersecting

pairs of families A, B S p was initiated by Moon [ Mo82 ]. She proved, using a

clever induction argument, that in the special case when p 1 = p 2 =

ↆ

··· = p n = k

for some k ≥ 3, every cross-intersecting pair A, B ↆ S p satisfies

k 2 n− 2 , | A |·| B |≤

with equality if and only if A = B = { x ∈ S p : x i = j } , for some i ∈

[ n ]and j [ k ]. In the case A = B , Moon's theorem had been discovered by

Berge [ Be74 ], Livingston [ Liv79 ], and Borg [ Bo08 ]. See also Stanton [ St80 ]. In his
report on Livingston's paper, published in the Mathematical Reviews , Kleitman
gave an extremely short proof for the case A = B , based on a shifting argument.
Zhang [ Zh13 ] established a somewhat weaker result, using a generalization of
Katona's circle method [ K72 ]. Note that for k = 2, we can take A = B to be
any family of 2 n− 1 vectors without containing a pair ( x 1 ,...,x n ) , ( y 1 ,...,y n )
with x i + y i =3forevery i . Then A is an intersecting family with

∈

2 =2 2 n− 2 ,

| A |

which is not of the type described in Moon's theorem.
Moon also considered r -cross-intersecting pairs in S p with p 1 = p 2 = ··· =

p n = k for some k>r + 1, and characterized all pairs for which | A |·| B | attains

its maximum, that is, we have

= k 2( n−r ) .

| A |·| B |

The assumption k>r + 1 is necessary. See Tokushige [ To13 ], for a somewhat
weaker result, using algebraic techniques.
Zhang [ Zh13 ] suggested that Moon's results may be extended to arbitrary
sequences of positive integers p =( p 1 ,...,p n ). The aim of this note is twofold:
(1) to establish such an extension under the assumption min i p i >r + 1, and (2)
to formulate a conjecture that covers essentially all other interesting cases. We
verify this conjecture in several special cases.
We start with the case r = 1, which has also been settled by Borg [ Bo14 ],
using different techniques.

Theorem 1. Let p =( p 1 ,...,p n ) be a sequence positive integers and let A, B ↆ

S p form a pair of cross-intersecting families of vectors.
We have

2 /k 2 ,where k = min i p i . Equality holds for the case

| A |·| B |≤| S p |

A = B = { x ∈ S p : x i = j } , whenever i ∈ [ n ] satisfies p i = k and j ∈ [ k ] .For

k

=2 , there are no other extremal cross-intersecting families.