Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655614 | Journal of Combinatorial Theory, Series A | 2010 | 6 Pages |
Abstract
A k-signed r-set on [n]={1,…,n} is an ordered pair (A,f), where A is an r-subset of [n] and f is a function from A to [k]. Families A1,…,Ap are said to be cross-intersecting if any set in any family Ai intersects any set in any other family Aj. Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of [n]. Our aim is to generalise Hilton's bound to one for families of k-signed r-sets on [n]. The main tool developed is an extension of Katona's cyclic permutation argument.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics