{
  "id": "2111.00532",
  "version": "v2",
  "published": "2021-10-31T16:16:28.000Z",
  "updated": "2024-02-06T14:06:22.000Z",
  "title": "Pure pairs. IX. Transversal trees",
  "authors": [
    "Alex Scott",
    "Paul Seymour",
    "Sophie Spirkl"
  ],
  "comment": "Accepted manuscript; see DOI for journal version",
  "journal": "SIAM Journal on Discrete Mathematics, Volume 38(1), 2024, pp. 645-667",
  "doi": "10.1137/21M1456509",
  "categories": [
    "math.CO"
  ],
  "abstract": "Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A pure pair in G is a pair X,Y of disjoint subsets of V(G) such that either all edges between X,Y are present or none are; and in the present context we are interested in pure pairs (X,Y) where each of X,Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2024-02-06T14:06:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "pure pair",
      "transversal trees",
      "disjoint subsets",
      "transversal subgraphs",
      "vertex set"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}