{
  "id": "1109.0417",
  "version": "v1",
  "published": "2011-09-02T11:59:25.000Z",
  "updated": "2011-09-02T11:59:25.000Z",
  "title": "An Analogue of Hilton-Milner Theorem for Set Partitions",
  "authors": [
    "Cheng Yeaw Ku",
    "Kok Bin Wong"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathcal{B}(n)$ denote the collection of all set partitions of $[n]$. Suppose $\\mathcal{A} \\subseteq \\mathcal{B}(n)$ is a non-trivial $t$-intersecting family of set partitions i.e. any two members of $\\A$ have at least $t$ blocks in common, but there is no fixed $t$ blocks of size one which belong to all of them. It is proved that for sufficiently large $n$ depending on $t$, \\[ |\\mathcal{A}| \\le B_{n-t}-\\tilde{B}_{n-t}-\\tilde{B}_{n-t-1}+t \\] where $B_{n}$ is the $n$-th Bell number and $\\tilde{B}_{n}$ is the number of set partitions of $[n]$ without blocks of size one. Moreover, equality holds if and only if $\\mathcal{A}$ is equivalent to \\[ \\{P \\in \\mathcal{B}(n): \\{1\\}, \\{2\\},..., \\{t\\}, \\{i\\} \\in P \\textnormal{for some} i \\not = 1,2,..., t,n \\}\\cup \\{Q(i,n)\\ :\\ 1\\leq i\\leq t\\} \\] where $Q(i,n)=\\{\\{i,n\\}\\}\\cup\\{\\{j\\}\\ :\\ j\\in [n]\\setminus \\{i,n\\}\\}$. This is an analogue of the Hilton-Milner theorem for set partitions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-09-02T11:59:25.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "set partitions",
      "hilton-milner theorem",
      "th bell number",
      "equality holds",
      "sufficiently large"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1109.0417Y"
    }
  }
}