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

also r -cross-intersecting. Indeed, if x B are r -intersecting vectors,

then φ i,j ( x, A )and φ i,j ( y, B ) are also r -intersecting, unless x and y have exactly
r common coordinates, one of them is x i = y i = j , and this common coordinate
gets ruined as φ i,j ( x, A )= x and φ i,j ( y, B )= φ i ( y ) (or vice versa). However,
this is impossible, because this would imply that the vector φ i ( x ) belongs to A ,
in spite of the fact that φ i ( x )and y

∈ A and y ∈

B are not r -intersecting.
If ( A, B )isa maximal r -cross-intersecting pair, then so is ( φ i,j ( A ) ,φ i,j ( B )).
When applying one of these shift operations does change the families A or B ,
then the total sum of all coordinates of all elements decreases. Therefore, after
shifting a finite number of times we arrive at a maximal pair of r -intersecting
families that cannot be changed by further shifting. We claim that this pair
( A, B ) is monotone. Let y

∈

B and y

B be arbitrary. We show that
B is monotone by showing that supp( y ) is not contained in supp( y ). Indeed,
by the maximality of the pair ( A, B ) and using the fact that y /

∈ ∈ S p \

∈ B, there

must exist x A such that x and y are not r -cross-intersecting, and hence ∈

supp( x ) supp( y ) r . Applying “projections” φ i to x in the coordinates | ∪ | >n −

supp( x ) supp( y ), we obtain x with supp( x ) = supp( x )

i supp( y ). The

shift operations φ i,j do not change the family A ,thus A must be closed for the
projections φ i and we have x

∈ ∩ \

∈ A . The supports of x and y are disjoint. Thus,

|

supp( x )

∪

supp( y )

|

, which is at most n

− r , as they

their Hamming distance is

are r -intersecting. Therefore, supp( x )

∪

supp( y ) = supp( x )

∪

supp( y ) is smaller

than supp( x ) supp( y ). This proves that B

is monotone. By symmetry, A is also monotone, which proves the first claim of
the lemma.
To prove the second claim, assume that p i

∪ supp( y ), showing that supp( y ) ↆ

[ n ]. Note that
Theorem 1 establishes the lemma in the case r =1,sofromnowonwecanassume
without loss of generality that r

≥ 3 for all i ∈

S p form a maximal r -cross-
intersecting pair. By the previous paragraph, this pair can be transformed into a
monotone pair by repeated applications of the shift operations φ i,j . Clearly, these
operations do not introduce new relevant coordinates. It remains to check that
the shifting operations do not produce balls from non-balls, that is, if A, B

≥ 2. Let A, B ↆ

S p
are maximal r -cross-intersecting families, and A = φ i,j ( A )and B = φ i,j ( B )
are balls, then so are A and B . In fact, by Lemma 4 it is sucient to prove that
one of them is a ball.
We saw that A and B must also form a maximal r -cross-intersecting pair.
Thus, by Lemma 4 , there is a set of coordinates T

ↆ

ↆ [ n ], a vector x 0 ∈ S p ,and

= r + l + m and that A and B are the Hamming balls
of radius l and m in coordinates T around the vector x 0 . We can assume that
i

radii l and m satisfying | T |

T , because otherwise A = A and we are done. We also have that ( x 0 ) i =1,
as otherwise A = φ i,j ( A ) is impossible. The vectors x

∈

∈ S p such that x i = j and

|{ k ∈ T : x k =( x 0 ) k }| = l +1

are called A -critical . Analogously, the vectors y

∈ S p such that y i = j and

|{ k ∈ T : y k =( x 0 ) k }| = m +1