{
  "id": "2006.12602",
  "version": "v1",
  "published": "2020-06-22T20:33:51.000Z",
  "updated": "2020-06-22T20:33:51.000Z",
  "title": "Analogues of Katona's and Milner's Theorems for two families",
  "authors": [
    "Peter Frankl",
    "Willie Wong H. W"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $n>s>0$ be integers, $X$ an $n$-element set and $\\mathscr{A}, \\mathscr{B}\\subset 2^X$ two families. If $|A\\cup B|\\le s$ for all $A\\in\\mathscr{A}, B\\in \\mathscr{B}$, then $\\mathscr{A}$ and $\\mathscr{B}$ are called cross $s$-union. Assuming that neither $\\mathscr{A}$ nor $\\mathscr{B}$ is empty, we prove several best possible bounds. In particular, we show that $|\\mathscr{A}|+|\\mathscr{B}|\\le 1+\\sum\\limits_{0\\le i\\le s}{{n}\\choose{i}}$. Supposing $n\\ge 2s$ and $\\mathscr{A},\\mathscr{B}$ are antichains, we show that $|\\mathscr{A}|+|\\mathscr{B}|\\le {{n}\\choose{1}}+{{n}\\choose{s-1}}$ unless $\\mathscr{A}=\\{\\emptyset\\}$ or $\\mathscr{B}=\\{\\emptyset\\}$. An analogous result for three families is established as well.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-22T20:33:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "F.2.2"
    ],
    "keywords": [
      "milners theorems",
      "element set",
      "antichains",
      "analogous result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}