Multiple cross-intersecting families of signed sets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:117

Article

Borg, Peter¹  Leader, Imre² 

[1] Univ Malta, Dept Math, MSD-2080 Msida, Malta

[2] Univ Cambridge, Dept Pure Math & Math Stat, Ctr Math Sci, Cambridge CB3 0WB, England

关键词: Extremal set theory;    Erdos-Ko-Rado Theorem;    Cross-intersecting families;    Signed sets;    Cyclic permutations;   

DOI  :  10.1016/j.jcta.2009.11.010

来源: Elsevier

【 摘 要 】

A k-signed r-set on [n] = {1,...,n} is an ordered pair (A, f), where A is an r-subset of In] and f is a function from A to [k]. Families A(1) ..., A(p) are said to be cross-intersecting if any set in any family A(i) intersects any set in any other family A(j). 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. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free