Intersecting generalised permutations

Abstract

For any positive integers k,r,n with r≤min{k,n}, let Pk,r,n be the family of all sets {(x1,y1),…,(xr,yr)} such that x1,…,xr are distinct elements of [k]={1,…,k} and y1,…,yr are distinct elements of [n]. The families Pn,n,n and Pn,r,n describe permutations of [n] and r-partial permutations of [n], respectively. If k≤n, then Pk,k,n describes permutations of k-element subsets of [n]. A family A of sets is said to be intersecting if every two members of A intersect. In this note we use Katona's elegant cycle method to show that a number of important Erdős-Ko-Rado-type results by various authors generalise as follows: the size of any intersecting subfamily A of Pk,r,n is at most (k−1r−1)(n−1)!(n−r)!, and the bound is attained if and only if A={A∈Pk,r,n:(a,b)∈A} for some a∈[k] and b∈[n].