{
  "id": "2009.09426",
  "version": "v1",
  "published": "2020-09-20T13:04:12.000Z",
  "updated": "2020-09-20T13:04:12.000Z",
  "title": "Pure pairs. IV. Trees in bipartite graphs",
  "authors": [
    "Alex Scott",
    "Paul Seymour",
    "Sophie Spirkl"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper we investigate the bipartite analogue of the strong Erdos-Hajnal property. We prove that for every forest $H$ and every $\\tau>0$ there exists $\\epsilon>0$, such that if $G$ has a bipartition $(A,B)$ and does not contain $H$ as an induced subgraph, and has at most $(1-\\tau)|A|\\cdot|B|$ edges, then there is a stable set in $G$ that contains at least $\\epsilon|V_i|$ vertices of $V_i$, for $i=1,2$. No graphs $H$ except forests have this property.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-20T13:04:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite graphs",
      "pure pairs",
      "strong erdos-hajnal property",
      "bipartite analogue",
      "induced subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}