{
  "id": "2105.03956",
  "version": "v1",
  "published": "2021-05-09T15:00:21.000Z",
  "updated": "2021-05-09T15:00:21.000Z",
  "title": "Pure pairs. V. Excluding some long subdivision",
  "authors": [
    "Alex Scott",
    "Paul Seymour",
    "Sophie Spirkl"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A pure pair in a graph $G$ is a pair $A,B$ of disjoint subsets of $V(G)$ such that $A$ is complete or anticomplete to $B$. Jacob Fox showed that for all $\\epsilon>0$, there is a comparability graph $G$ with $n$ vertices, where $n$ is large, in which there is no pure pair $A,B$ with $|A|,|B|\\ge \\epsilon n$. He also proved that for all $c>0$ there exists $\\epsilon>0$ such that for every comparability graph $G$ with $n>1$ vertices, there is a pure pair $A,B$ with $|A|,|B|\\ge \\epsilon n^{1-c}$; and conjectured that the same holds for every perfect graph $G$. We prove this conjecture and strengthen it in several ways. In particular, we show that for all $c>0$, and all $\\ell_1, \\ell_2\\ge 4c^{-1}+9$, there exists $\\epsilon>0$ such that, if $G$ is an $(n>1)$-vertex graph with no hole of length exactly $\\ell_1$ and no antihole of length exactly $\\ell_2$, then there is a pure pair $A,B$ in $G$ with $|A|\\ge \\epsilon n$ and $|B|\\ge \\epsilon n^{1-c}$. This is further strengthened, replacing excluding a hole by excluding some long subdivision of a general graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-09T15:00:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "pure pair",
      "long subdivision",
      "comparability graph",
      "vertex graph",
      "general graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}