An Erdős--Ko--Rado theorem for partial permutations (Q817754)

An \(r\)-partial permutation of \([n]\) is an ordered pair \((A,f)\) where \(A\subset [n]\) has \(r\) elements and \(f:A\rightarrow [n]\) is an injective map. Two such animals are intersecting if their set components contain a common element having the same image under their respective maps. The main result of this paper is that the Erdős-Ko-Rado families have always maximal cardinality among the intersecting systems. Furthermore the authors show that for the majority of cases the maximum pairwise intersecting families of partial permutations have the familiar Erdős-Ko-Rado structure.