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

Proof. Let us fix r, n, p, i, A, and B as in the lemma. By Lemma 4 , if a coordinate
is irrelevant for A , then it is also irrelevant for B and vice versa.
In the case n = r ,wehave A = B and this family must be a singleton, so
that the lemma is trivially true. From now on, we assume that n>r and hence
the notion of r -cross-intersecting families is meaningful for n

− 1 coordinates.

Let q =( p 1 ,...,p i− 1 ,p i +1 ,...,p n ). For any l ∈ [ p i ], let

A l =

{ x ∈ A : x i = l } ,

B l =

,
and let A l and B l stand for the families obtained from A l and B l , respectively,
by dropping their i th coordinates. By definition, we have A l ,B l ↆ

{ y ∈ B : y i = l }

S q ,and | A | =

l |

= l |

[ p i ] ,
the families A l and B m are r -cross-intersecting, since the vectors in A l differ from
the vectors in B m in the i th coordinate, and therefore the r indices where they
agree must be elsewhere.
Let Z denote the maximum product

A l | and | B | B l | . Furthermore, for any two distinct elements l, m ∈

A ∗ |·| B ∗ |

| of an r -cross-intersecting

pair A ∗ ,B ∗

= m .
Adding an irrelevant i th coordinate to the maximal r -cross-intersecting pair
A ∗ ,B ∗ ↆ

ↆ S q .Wehave | A l |·| B m |≤ Z for all l, m ∈ [ p i ] with l

S q , we obtain a pair A ∗ ,B ∗ ↆ S p with | A ∗ |·| B ∗ |

= p i Z . Thus, using

the maximality of A and B ,wehave

| A |·| B |≥ p i Z .Let l 0 be chosen so as to

maximize | A l 0 |·| B l 0 | , and let c = | A l 0 |·| B l 0 | /Z .

Assume first that c ≤ 1. Then we have

p i Z Z = p i Z.

≤| A |·| B | =

[ p i ] |

A l |·| B m |≤

l,m ∈ l,m ∈ [ p i ]

Hence, we must have equality everywhere. This yields that c = 1 and that A l
and B m form a maximal r -cross-intersecting pair for all l, m

∈ [ p i ], l = m . This

also implies that | A l | = | A m | for l, m ∈ [ p i ], from where the statement of the

lemma follows, provided that p i =2.
If p i ≥ 3, then all families A l must be equal to one another, since one member

in a maximal r -cross-intersecting family determines the other (by Lemma 4 ). This
contradicts our assumption that the i th coordinate was relevant for A .
Thus, we may assume that c> 1.
For m

∈ [ p i ], m = l 0 ,wehave | A l 0 |·| B m |≤ Z = | A l 0 |·| B l 0 | /c .Thus,

| B m |≤| B l 0 | /c, (1)

= m∈ [ p i ] | which yields that | B | B m |≤ (1 + ( p i − 1) /c ) | B l 0 | . By symmetry, we

also have

| A m |≤| A l 0 | /c (2)

for m = l 0 and | A |≤ (1 + ( p i − 1) /c ) | A l 0 | . Combining these inequalities, we

obtain

p i Z

1) /c ) 2 1) /c ) 2 cZ.

≤| A |·| B |≤

(1 + ( p n −

| A l 0 |·| B l 0 |

=(1+( p i −