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

to B or neither of them does. This holds for every vector x , implying that j is
irrelevant for the family B and thus also for A .
As there are no relevant coordinates for A and B outside the set I of coor-
dinates with p i =2,wecanchooseaset W of functions from I to [2] such that
A = A W . This makes

B = { y ∈ S p : y intersects all x ∈ A } = B W .

=2 |I|− 1 .
The size vector p =(2 ,..., 2) of length n is well studied. In this case, S p is the
n -dimensional hypercube. If r> 1, then all maximal r -cross-intersecting pairs
have an unbounded number of relevant coordinates, as a function of n . Indeed,
the density

2 / 4 if and only if

We have | A | + | B | = | S p | and | A |·| B | = | S p | | W |

2 is at most 1 / 4 for cross-intersecting pairs A, B

S p ,
and strictly less than 1 / 4for r -cross-intersecting families if r> 1. Furthermore,
if the number of relevant coordinates is bounded, then this density is bounded
away from 1 / 4, while if A = B is the ball of radius ( n

| A |·| B | / | S p | ↆ

− r ) / 2 in all the coordinates,

then the same density approaches 1 / 4.
One can also find many maximal 2-cross-intersecting pairs that are not balls.
For example, in the 3-dimensional hypercube the families A =

{

0 , 0 , 0) , (0 , 1 , 1)

}

and B =

{

(0 , 0 , 1) , (0 , 1 , 0)

}

form a maximal 2-cross-intersecting pair.
Finally, we mention that there is a simple connection between the problem
discussed in this paper and a question related to communication complexity.
Consider the following two-person communication game: Alice and Bob each
receive a vector from S p , and they have to decide whether the vectors are r -
intersecting. In the communication matrix of such a game, the rows are indexed
by the possible inputs of Alice, the columns by the possible inputs of Bob, and an
entry of the matrix is 1 or 0 corresponding to the “yes” or “no” output the players
have to compute for the corresponding inputs. In the study of communication
games, the submatrices of this matrix in which all entries are equal play a special
role. The largest area of an all-1 submatrix is the maximal value of

| A |·| B | for

r -cross-intersecting families A, B ↆ S p .

Acknowledgment. We are indebted to G. O. H. Katona, R. Radoicic, and D. Scheder
for their valuable remarks, and to an anonymous referee for calling our attention to
the manuscript of Borg [ Bo14 ].

References

[AhK98] Ahlswede, R., Khachatrian, L.H.: A diametric theorem for edges. The dia-
metric theorem in Hamming spaces—optimal anticodes. Adv. Appl. Math.
20 (4), 429-449 (1998)
[Be74] Berge, C.: Nombres de coloration de l'hypegraphe h -parti complet. In:
Hypergraph Seminar. Lecture Notes in Mathematics, vol. 411, pp. 13-20.
Springer, Heidelberg (1974)
[Bol86] Bollobas, B.: Combinatorics: Set Systems, Hypergraphs, Families of Vec-
tors and Combinatorial Probability. Cambridge University Press, Cambridge
(1986)