{
  "id": "1706.06994",
  "version": "v1",
  "published": "2017-06-21T16:32:40.000Z",
  "updated": "2017-06-21T16:32:40.000Z",
  "title": "Disjoint pairs in set systems with restricted intersection",
  "authors": [
    "António Girão",
    "Richard Snyder"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The problem of bounding the size of a set system under various intersection restrictions has a central place in extremal combinatorics. We investigate the maximum number of disjoint pairs a set system can have in this setting. In particular, we show that for any pair of set systems $(\\mathcal{A}, \\mathcal{B})$ which avoid a cross-intersection of size $t$, the number of disjoint pairs $(A, B)$ with $A \\in \\mathcal{A}$ and $B \\in \\mathcal{B}$ is at most $\\sum_{k=0}^{t-1}\\binom{n}{k}2^{n-k}$. This implies an asymptotically best possible upper bound on the number of disjoint pairs in a single $t$-avoiding family $\\mathcal{F} \\subset \\mathcal{P}[n]$. We also study this problem when $\\mathcal{A}$, $\\mathcal{B} \\subset [n]^{(r)}$ are both $r$-uniform, and show that it is closely related to the problem of determining the maximum of the product $|\\mathcal{A}||\\mathcal{B}|$ when $\\mathcal{A}$ and $\\mathcal{B}$ avoid a cross-intersection of size $t$, and $n \\ge n_0(r, t)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-21T16:32:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "set system",
      "disjoint pairs",
      "restricted intersection",
      "maximum number",
      "central place"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}