PURE PAIRS VI: EXCLUDING AN ORDERED TREE

Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

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| . We generalize this to all ordered forests, at the cost of a slightly worse bound: we prove that, for every ordered forest F, every ordered graph G with at least two vertices that does not contain F or its complement as an induced subgraph has a pure pair of size | G| 1 - o(1)

Original languageEnglish (US)
Pages (from-to)170-187
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume36
Issue number1
DOIs
StatePublished - 2022

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • induced subgraphs
  • ordered graphs
  • trees

Fingerprint

Dive into the research topics of 'PURE PAIRS VI: EXCLUDING AN ORDERED TREE'. Together they form a unique fingerprint.

Cite this