{
  "id": "1403.2344",
  "version": "v1",
  "published": "2014-03-10T18:57:13.000Z",
  "updated": "2014-03-10T18:57:13.000Z",
  "title": "Intersecting generalised permutations",
  "authors": [
    "Peter Borg",
    "Karen Meagher"
  ],
  "comment": "8 pages, submitted",
  "categories": [
    "math.CO"
  ],
  "abstract": "For any positive integers $k,r,n$ with $r \\leq \\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 \\leq 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\\H{o}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 ${k-1 \\choose r-1}\\frac{(n-1)!}{(n-r)!}$, and the bound is attained if and only if $\\mathcal{A} = \\{A \\in \\mathcal{P}_{k,r,n} \\colon (a,b) \\in A\\}$ for some $a \\in [k]$ and $b \\in [n]$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-03-10T18:57:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "20B30"
    ],
    "keywords": [
      "intersecting generalised permutations",
      "distinct elements",
      "katonas elegant cycle method",
      "partial permutations",
      "authors generalise"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1403.2344B"
    }
  }
}