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

We will proceed in two steps. First we argue, using entropies , that the number of
relevant coordinates in a maximal r -cross-intersecting family is bounded. Then
we apply combinatorial methods to prove the conjecture under the assumption
that the number of relevant coordinates is small.
In the case when there are many relevant coordinates for a pair of maximal
r -cross-intersecting families, we use entropies to bound the size of the families
and to prove

Theorem 5. S p

form a maximal pair of r -cross-intersecting families and let T be the set of
coordinates that are relevant for A or B . Then neither the size of A nor the
size of B can exceed

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

S p |
i∈T ( p i −

|

.

1) 1 − 2 /p i

We use this theorem to bound the number of relevant coordinates i with
p i > 2. The number of relevant coordinates i with p i = 2 can be unbounded; see
Sect. 5 .

Theorem 6. Let 1 ≤ r ≤ n ,let p =( p 1 ,...,p n ) be a size vector and let A, B ↆ

S p form a maximal pair of r -cross-intersecting families.
For the set of coordinates T relevant for A or B , we have
r

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

i =1 i∈T

which implies that |{ i ∈ T : p i > 2 }| < 5 r .

We can characterize the maximal r -cross-intersecting pairs for all size vectors p
satisfying min p i >r + 1, and in many other cases.

Theorem 7. Let 1 ≤ r ≤ n ,let p =( p 1 ,...,p n ) be a size vector with p 1 ≤ p 2 ≤

··· ≤ S p form a pair of r -cross-intersecting families.

1. If p 1 >r +1 , we have

p n and let A, B ↆ

|≤ i = r +1 p i .Incaseofequality, A = B holds
and this family can be obtained by fixing r coordinates in S p .
2. If p 1 = r +1 > 7 , we have

| A |·| B

|≤ i = r +1 p i . In case of equality, A = B
holds and this family can be obtained either by fixing r coordinates in S p or
by taking a Hamming ball of radius 1 in r +2 coordinates i , all satisfying
p i = r +1 .
3. There is a function t ( r )= o ( r ) such that if p 1

| A |·| B

2 r/ 3+ t ( r ) and ( A, B ) is
a maximal r -cross-intersecting pair, then the families A and B are balls of
radius 0 or 1 in at most r +2 coordinates.

≥

The proof of Theorem 7 relies on the following result.

Theorem 8. Let 1 ≤ r ≤ n and let p be a size vector of length n with p i > 2

for all i S p is a maximal pair of r -cross-intersecting families

and at most r +2 coordinates are relevant for them, then A and B are balls of
radius 0 or 1.

∈ [ n ] .If A, B ↆ