{
  "id": "2312.15572",
  "version": "v1",
  "published": "2023-12-25T00:53:40.000Z",
  "updated": "2023-12-25T00:53:40.000Z",
  "title": "Induced subgraph density. VI. Bounded VC-dimension",
  "authors": [
    "Tung Nguyen",
    "Alex Scott",
    "Paul Seymour"
  ],
  "comment": "10 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We confirm a conjecture of Fox, Pach, and Suk, that for every $d>0$, there exists $c>0$ such that every $n$-vertex graph of VC-dimension at most $d$ has a clique or stable set of size at least $n^c$. This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erd\\H{o}s-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lov\\'asz and Szegedy, the method of iterative sparsification introduced in the series, and a technique employed in our recent proof of the Erd\\H{o}s-Hajnal conjecture for the five-vertex path.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-25T00:53:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "induced subgraph density",
      "bounded vc-dimension",
      "conjecture",
      "ultra-strong regularity lemma",
      "result extends"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}