{
  "id": "0807.3702",
  "version": "v1",
  "published": "2008-07-23T15:41:35.000Z",
  "updated": "2008-07-23T15:41:35.000Z",
  "title": "On families of subsets with a forbidden subposet",
  "authors": [
    "Jerrold R. Griggs",
    "Linyuan Lu"
  ],
  "comment": "19 pages, submitted to CPC",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\F\\subset 2^{[n]}$ be a family of subsets of $\\{1,2,..., n\\}$. For any poset $H$, we say $\\F$ is $H$-free if $\\F$ does not contain any subposet isomorphic to $H$. Katona and others have investigated the behavior of $\\La(n,H)$, which denotes the maximum size of $H$-free families $\\F\\subset 2^{[n]}$. Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets $H$, for which $\\La(n,H)$ can be determined asymptotically as $n\\to\\infty$ for various posets $H$, including two-end-forks, up-down trees, and cycles $C_{4k}$ on two levels.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-07-23T15:41:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "forbidden subposet",
      "extremal graph theory",
      "up-down trees",
      "subposet isomorphic",
      "probability theory"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0807.3702G"
    }
  }
}