Cross-Intersecting Families of Partial Permutations
Cross-Intersecting Families of Partial Permutations
For positive integers r and n with $r\leq n$, let $\mathcal{P}_{n,r}$ 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 $[n]:=\{1,\dots,n\}$ and $y_1,\dots,y_r$ are also distinct elements of $[n]$. $\mathcal{P}_{n,n}$ describes permutations of $[n]$. For $r<n$, $\mathcal{P}_{n,r}$ describes r-partial permutations of $[n]$. Families $\mathcal{A}_1,\dots,\mathcal{A}_k$ of …