Intersecting generalised permutations

Abstract

For any positive integers $k,r,n$ with $r\le \min \{k,n\}$, let ${\mathcal{P}}_{k,r,n}$ be the family of all sets $\{(x_1,y_1),\dots ,(x_r,y_r)\}$ such that $x_1,\dots ,x_r$ are distinct elements of $[k]=\{1,\dots ,k\}$ and $y_1,\dots ,y_r$ are distinct elements of $[n]$. The families ${\mathcal{P}}_{n,n,n}$ and ${\mathcal{P}}_{n,r,n}$ describe permutations of $[n]$ and $r$-partial permutations of $[n]$, respectively. If $k\le n$, then ${\mathcal{P}}_{k,k,n}$ describes permutations of $k$-element subsets of $[n]$. A family $\mathcal{A}$ of sets is said to be intersecting if every two members of $\mathcal{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 $\mathcal{A}$ of ${\mathcal{P}}_{k,r,n}$ is at most $\left(\genfrac{}{}{0ex}{}{k-1}{r-1}\right)\frac{(n-1)!}{(n-r)!}$, and the bound is attained if and only if $\mathcal{A}=\{A\in {\mathcal{P}}_{k,r,n}:(a,b)\in A\}$ for some $a\in [k]$ and $b\in [n]$.

8 pages, submitted