Cross-intersecting families of permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:117

Article

Borg, Peter

关键词: Cross-intersecting families;    Intersecting families;    Permutations;   

DOI  :  10.1016/j.jcta.2009.07.003

来源: Elsevier

【 摘 要 】

For positive integers r and n with r <= n, let P-r,P-n be the family of all sets {(1,y(1)), (2, y(2)), (r, y(r))} such that y(1), y(2),...,y(r) are distinct elements of [n] = {1, 2,..., n}. P-n,P-n describes permutations of [n]. For r < n, P-r,P-n describes permutations of r-element subsets of [n]. Families A(1), A(2), A(k) of sets are said to be cross-intersecting if, for any distinct i and j in [k] any set in A(i) intersects any set in A(j). For any r, n and k >= 2, we determine the cases in which the sum of sizes of cross-intersecting subfamilies A(1), A(2),...,A(k) of P-r,P-n is a maximum, hence solving a recent conjecture (suggested by the author). (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free