{
  "id": "1911.00487",
  "version": "v1",
  "published": "2019-11-01T17:52:15.000Z",
  "updated": "2019-11-01T17:52:15.000Z",
  "title": "The extremal number of Venn diagrams",
  "authors": [
    "Peter Keevash",
    "Imre Leader",
    "Jason Long",
    "Adam Zsolt Wagner"
  ],
  "comment": "11 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We show that there exists an absolute constant $C>0$ such that any family $\\mathcal{F}\\subset \\{0,1\\}^n$ of size at least $Cn^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $Cn^3$ contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the $Cn^{3.75}$ bound of Gupta, Lee and Li and is sharp up to the value of the constant.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-01T17:52:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "venn diagram",
      "extremal number",
      "absolute constant",
      "dual vc-dimension"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}