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

Cross-Intersecting Families of Vectors

B

Janos Pach 1(

) and Gabor Tardos 2

1 Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland
[e-mail]
2 Renyi Institute of Mathematics, Budapest, Hungary
[e-mail]

Abstract. Given a sequence of positive integers p =( p 1 ,...,p n ), let S p
denote the family of all sequences of positive integers x =( x 1 ,...,x n )
such that x i

≤ p i for all i . Two families of sequences (or vectors),

A, B ↆ if no matter how we

select x ∈ A and y ∈ B , there are at least r distinct indices i such
that x i = y i . We determine the maximum value of |A|·|B| over all
pairs of r -cross-intersecting families and characterize the extremal pairs
for r ≥ 1, provided that min p i >r + 1. The case min p i ≤ r +1 is
quite different. For this case, we have a conjecture, which we can ver-
ify under additional assumptions. Our results generalize and strengthen
several previous results by Berge, Frankl, Furedi, Livingston, Moon, and
Tokushige, and answers a question of Zhang. The special case r =1has
also been settled recently by Borg.

S p ,aresaidtobe r-cross-intersecting

1 Introduction

The Erdos-Ko-Rado theorem [ EKR61 ] states that for n 2 k , every family of

pairwise intersecting k -element subsets of an n -element set consists of at most

≥

n− 1

k− 1 subsets, as many as the star-like family of all subsets containing a fixed
element of the underlying set. This was the starting point of a whole new area
within combinatorics: extremal set theory; see [ GK78 , Bol86 , DeF83 , F95 ]. The
Erdos-Ko-Rado theorem has been extended and generalized to other structures:
to multisets, divisors of an integer, subspaces of a vector space, families of per-
mutations, etc. It was also generalized to “cross-intersecting” families, i.e., to
families A and B with the property that every element of A intersects all ele-
ments of B ; see Hilton [ Hi77 ], Moon [ Mo82 ], and Pyber [ Py86 ].
For any positive integer k , we write [ k ] for the set

{ 1 ,...,k } . Given a sequence

of positive integers p =( p 1 ,...,p n ), let

S p =[ p 1 ] ×···× [ p n ]= { ( x 1 ,...,x n ): x i ∈ [ p i ]for i ∈ [ n ] } .

J. Pach is supported by OTKA under ERC projects GraDR and ComPoSe 10-
EuroGIGA-OP-003, and by Swiss National Science Foundation Grants 200020-
144531 and 200021-137574. G. Tardos is supported by OTKA grant NN-102029,
an NSERC Discovery grant, the “Lendulet” project of the Hungarian Academy of
Sciences and by EPFL.