Uniform s-Cross-Intersecting Families

In this paper we study a question related to the classical Erdos-Ko-Rado theorem, which states that any family of k-element subsets of the set [n] = {1,..., n} in which any two sets intersect has cardinality at most ((n-1)(k-1)). We say that two non-empty families A, B subset of (([n])(k)) are s-cross-intersecting if, for any A is an element of A, B is an element of B, we have |A boolean AND B| >= s. In this paper we determine the maximum of |A| + |B| for all n. This generalizes a result of Hilton and Milner, who determined the maximum of |A| + |B| for nonempty 1-cross-intersecting families.


Published in:
Combinatorics Probability & Computing, 26, 4, 517-524
Year:
2017
Publisher:
New York, Cambridge Univ Press
ISSN:
0963-5483
Laboratories:




 Record created 2017-09-05, last modified 2018-01-28


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)