{
  "id": "1210.7470",
  "version": "v1",
  "published": "2012-10-28T15:37:56.000Z",
  "updated": "2012-10-28T15:37:56.000Z",
  "title": "EKR sets for large $n$ and $r$",
  "authors": [
    "Benjamin Bond"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\A\\subset\\binom{[n]}{r}$ be a compressed, intersecting family and let $X\\subset[n]$. Let $\\A(X)={A\\in\\A:A\\cap X\\ne\\emptyset}$ and $\\S_{n,r}=\\binom{[n]}{r}({1})$. Motivated by the Erd\\H{o}s-Ko-Rado theorem, Borg asked for which $X\\subset[2,n]$ do we have $|\\A(X)|\\le|\\S_{n,r}(X)|$ for all compressed, intersecting families $\\A$? We call $X$ that satisfy this property EKR. Borg classified EKR sets $X$ such that $|X|\\ge r$. Barber classified $X$, with $|X|\\le r$, such that $X$ is EKR for sufficiently large $n$, and asked how large $n$ must be. We prove $n$ is sufficiently large when $n$ grows quadratically in $r$. In the case where $\\A$ has a maximal element, we are able to sharpen this bound to $n>\\varphi^{2}r$ implies $|\\A(X)|\\le|\\S_{n,r}(X)|$. We conclude by giving a generating function that speeds up computation of $|\\A(X)|$ in comparison with the na\\\"{i}ve methods.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-10-28T15:37:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "sufficiently large",
      "borg classified ekr sets",
      "property ekr",
      "maximal element",
      "intersecting family"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.7470B"
    }
  }
}