{
  "id": "1408.5783",
  "version": "v1",
  "published": "2014-08-25T14:56:01.000Z",
  "updated": "2014-08-25T14:56:01.000Z",
  "title": "An improvement of the general bound on the largest family of subsets avoiding a subposet",
  "authors": [
    "Dániel Grósz",
    "Abhishek Methuku",
    "Casey Tompkins"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $La(n,P)$ be the maximum size of a family of subsets of $[n]= \\{1,2, \\ldots, n \\}$ not containing $P$ as a (weak) subposet, and let $h(P)$ be the length of a longest chain in $P$. The best known upperbound for $La(n,P)$ in terms of $|P|$ and $h(P)$ is due to Chen and Li, who showed that $La(n,P) \\le \\frac{1}{m+1} \\left(|P| + \\frac{1}{2}(m^2 +3m-2)(h(P)-1) -1 \\right) {\\binom {n} {\\lfloor n/2 \\rfloor}}$ for any fixed $m \\ge 1$. In this paper we show that $La(n,P) \\le \\frac{1}{2^{k-1}} \\left(|P| + (3k-5)2^{k-2}(h(P)-1) - 1 \\right) {n \\choose \\left\\lfloor n/2\\right\\rfloor }$ for any fixed $k \\ge 2$, thereby improving the best known upper bound. By choosing $k$ appropriately, we obtain that $La(n,P) = O\\left( h(P) \\log_2\\left(\\frac{|P|}{h(P)}+2\\right) \\right) {n \\choose \\left\\lfloor \\frac{n}{2}\\right\\rfloor }$ as a corollary, which we show is best possible for general $P$. We also give a different proof of this corollary by using bounds for generalized diamonds.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-08-25T14:56:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "general bound",
      "subsets avoiding",
      "largest family",
      "improvement",
      "longest chain"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1408.5783G"
    }
  }
}