Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424183 | European Journal of Combinatorics | 2014 | 14 Pages |
Abstract
We say that a set A  t-intersects a set B if A and B have at least t common elements. A family A of sets is said to be t-intersecting if each set in A  t-intersects all the other sets in A. Families A1,A2,â¦,Ak are said to be cross-t-intersecting if for any i and j in {1,2,â¦,k} with iâ j, every set in Ai  t-intersects every set in Aj. We prove that for any finite family F that has at least one set of size at least t, there exists an integer κâ¤|F| such that for any kâ¥Îº, both the sum and the product of sizes of k cross-t-intersecting subfamilies A1,â¦,Ak (not necessarily distinct or non-empty) of F are maxima if A1=â¯=Ak=L for some largest t-intersecting subfamily L of F. We then study the smallest possible value of κ and investigate the case k<κ; this includes a cross-intersection result for straight lines that demonstrates that it is possible to have F and κ such that for any k<κ, the configuration A1=â¯=Ak=L is neither optimal for the sum nor optimal for the product. We also outline solutions for various important families F, and we provide solutions for the case when F is a power set.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Peter Borg,