{
  "id": "1110.0099",
  "version": "v1",
  "published": "2011-10-01T13:41:52.000Z",
  "updated": "2011-10-01T13:41:52.000Z",
  "title": "Two-part set systems",
  "authors": [
    "Dániel Gerbner",
    "Péter L. Erd\\Hos",
    "Nathan Lemons",
    "Dhruv Mubayi",
    "Cory Palmer",
    "Balázs Patkós"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The two part Sperner theorem of Katona and Kleitman states that if $X$ is an $n$-element set with partition $X_1 \\cup X_2$, and $\\cF$ is a family of subsets of $X$ such that no two sets $A, B \\in \\cF$ satisfy $A \\subset B$ (or $B \\subset A$) and $A \\cap X_i=B \\cap X_i$ for some $i$, then $|\\cF| \\le {n \\choose \\lfloor n/2 \\rfloor}$. We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfiy various combinations of these properties on one or both parts $X_1$, $X_2$. Along the way, we prove the following new result which may be of independent interest: let $\\cF, \\cG$ be families of subsets of an $n$-element set such that $\\cF$ and $\\cG$ are both intersecting and cross-Sperner, meaning that if $A \\in \\cF$ and $B \\in \\cG$, then $A \\not\\subset B$ and $B \\not\\subset A$. Then $|\\cF| +|\\cG| < 2^{n-1}$ and there are exponentially many examples showing that this bound is tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-10-01T13:41:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "two-part set systems",
      "element set",
      "part sperner theorem",
      "independent interest",
      "intersection property"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.0099G"
    }
  }
}