2014/03/10 by Peter Borg, Borg, Peter, Karen Meagher +1
Mathematics · #05D05 (Primary) 20B30 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1403.2344
openalex publication_date 2014/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-1 \choose r-1((n-1)!)/((n-r)!), and the bound is attained if and only if A = \A ∈ Pk,r,n \colon (a,b) ∈ A\ for some a ∈ [k] and b ∈ [n].