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

Now we can quickly finish the proof of Theorem 1 .

Proof of Theorem 1. Notice that Lemma 2 implies Theorem 1 , whenever k =
min i p i ≥ 3. It remains to verify the statement for k =1and k =2.For k =1,

it follows from the fact that all pairs of vectors in S p are intersecting, thus the
only maximal cross-intersecting pair is A = B = S p .
Suppose next that k =2.For x S p ,let x S p be defined by x i =

∈ ∈

x is a permutation of S p . Clearly, x
and x are not intersecting, so we either have x/

( x i +1mod p i )for i ∈ [ n ]. Note that x ₒ

A or x ∈ ∈ / B . As a consequence,

2 / 4,

we obtain that | A | + | B |≤| S p | , which, in turn, implies that | A |·| B |≤| S p |

as claimed. It also follows that all maximal pairs satisfy | A | = | B | = | S p | / 2.

3 Using Entropy: Proofs of Theorems 5 and 6

Proof of Theorem 5. Let r, n, p, A, B and T be as in the theorem. Let us write y
for a randomly and uniformly selected element of B . Lemma 9 implies that, for
each i

∈ T , there exists a value l i ∈ [ p i ] such that

Pr [ y i = l i ] ≥ 1 − 1 /p i . (3)

We bound the entropy H ( y i )of y i from above by the entropy of the indicator
variable of the event y i = l i plus the contribution coming from the entropy of y i
assuming y i

= l i :

H ( y i ) ≤ h (1 − 1 /p i )+(1 /p i ) log( p i − 1) = log p i − (1 − 2 /p i ) log( p i − 1) ,

where h ( z )= − z log z − (1 − z ) log(1 − z ) is the entropy function, and we used

that 1 − 1 /p i ≥ 1 / 2.

For any i ∈ [ n ] \ T , we use the trivial estimate H ( y i ) ≤ log p i . By the subad-

ditivity of the entropy, we obtain

| B |

= H ( y )

≤ H ( y i ) ≤

(log p i −

−

2 /p i ) log( p i − log p i , log (1 1)) +

i∈T

i∈ [ n ] i∈ [ n ] \T

or, equivalently,

p i S p |

i∈T ( p i −

|

| B |≤ p i =

1) 1 − 2 /p i 1) 1 − 2 /p i ( p i −

i ∈ T

i∈ [ n ] \T

as required. The bound on | A | follows by symmetry and completes the proof of

the theorem.

Theorem 6 is a simple corollary of Theorem 5 .

Proof of Theorem 6. Fixing the first r coordinates, we obtain the family

C = { x ∈ S p : x i = 1 for all i ∈ [ r ] } .