An Erdős–Ko–Rado theorem for partial permutations Original Research Article

Let [n][n] denote the set of positive integers {1,2,…,n}{1,2,…,n}. An r-partial permutation of [n][n] is a pair (A,f)(A,f) where A⊆[n]A⊆[n], |A|=r|A|=r and f:A→[n]f:A→[n] is an injective map. A set AA of r-partial permutations is intersecting if for any (A,f)(A,f), (B,g)∈A(B,g)∈A, there exists x∈A∩Bx∈A∩B such that f(x)=g(x)f(x)=g(x). We prove that for any intersecting family AA of r-partial permutations, we have View the MathML source|A|⩽n-1r-1((n-1)!/(n-r)!). It seems rather hard to characterize the case of equality. For 8⩽r⩽n-38⩽r⩽n-3, we show that equality holds if and only if there exist x0x0 and ε0ε0 such that AA consists of all (A,f)(A,f) for which x0∈Ax0∈A and f(x0)=ε0f(x0)=ε0