Cross-intersecting families of partial permutations

Abstract

For positive integers r and n with r ≤ n, let Pn, r be the family of all sets {(x1, y1), ⋯, (xr, yr)} such that x1, ⋯, xr are distinct elements of [n]:= {1, ⋯, n} and y1, ⋯, yr are also distinct elements of [n]. Pn, n describes permutations of [n]. For r < n, Pn, r describes r-partial permutations of [n]. Families A1, ⋯, 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. A sharp bound for the sum of sizes of cross-intersecting subfamilies of P n, n has recently been established by the author. We generalize this bound by showing that, if A1, ⋯, Ak are cross-intersecting subfamilies of Pn, rthen (i) ∑ i=1k|Ai| ≤ (n/r) n!/(n-r)! if k ≤ n/r and (ii) ∑ i=1k|Ai| ≤ k(n-1/n-1) (n-1)!/(n-1)! if k < n2/r. We also determine the structures for which the bound is attained when r< n. Our main tool is an extension of Katona's cyclic permutation method.