Cross-intersecting families of permutations

Abstract

For positive integers r and n with r n, let Pr,n be the family of all sets {(1, y1), (2, y2),. . . , (r, yr)} such that y1, y2,..., yr are distinct elements of [n]={1, 2,...,n}. Pn,n describes permutations of [n]. For r < n, Pr,n describes permutations of r-element subsets of [n]. Families A1,A2,...,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k 2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A1,A2,...,Ak of Pr,n is a maximum, hence solving a recent conjecture.