@article{1d035ec332774198941f29e2007717e8,
title = "PURE PAIRS VI: EXCLUDING AN ORDERED TREE",
abstract = "A pure pair in a graph G is a pair (Z1, Z2) of disjoint sets of vertices such that either every vertex in Z1 is adjacent to every vertex in Z2, or there are no edges between Z1 and Z2. With Maria Chudnovsky, we recently proved that, for every forest F, every graph G with at least two vertices that does not contain F or its complement as an induced subgraph has a pure pair (Z1, Z2) with | Z1|, | Z2| linear in | G| . Here we investigate what we can say about pure pairs in an ordered graph G, when we exclude an ordered forest F and its complement as induced subgraphs. Fox showed that there need not be a linear pure pair; but Pach and Tomon showed that if F is a monotone path, then there is a pure pair of size c| G| /log | G| .",
keywords = "induced subgraphs, ordered graphs, trees",
author = "Alex Scott and Paul Seymour and Sophie Spirkl",
note = "Funding Information: \ast Received by the editors September 21, 2020; accepted for publication (in revised form) July 6, 2021; published electronically January 6, 2022. https://doi.org/10.1137/20M1368331 Funding: The work of the second author was supported by AFOSR grant A9550-19-1-0187 and NSF grant DMS-1800053. The work of the third author is based upon work supported by NSF grant DMS-1802201. \dagger Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK (scott@maths.ox.ac.uk). \ddagger Department of Mathematics, Princeton University, Princeton, NJ 08544 USA (pds@math. princeton.edu). \S Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, N2L 3E9, Canada (sspirkl@uwaterloo.ca). This author's work was performed while at Princeton University. Publisher Copyright: {\textcopyright} 2022 Society for Industrial and Applied Mathematics",
year = "2022",
doi = "10.1137/20M1368331",
language = "English (US)",
volume = "36",
pages = "170--187",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",
}