@article{9602,
  abstract     = {An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer k, there exists a constant ck > 0 such that any ordered graph G on n vertices with the property that neither G nor its complement contains an induced monotone path of size k, has either a clique or an independent set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs.
A key idea of the above paper was to show that any unordered graph on n vertices that does not contain an induced path of size k, and whose maximum degree is at most c(k)n for some small c(k) > 0, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for k ≥ 3, by a construction of Fox. We provide some further examples showing that this statement also fails for ordered graphs avoiding other ordered trees.},
  author       = {Pach, János and Tomon, István},
  issn         = {0095-8956},
  journal      = {Journal of Combinatorial Theory. Series B},
  pages        = {21--37},
  publisher    = {Elsevier},
  title        = {{Erdős-Hajnal-type results for monotone paths}},
  doi          = {10.1016/j.jctb.2021.05.004},
  volume       = {151},
  year         = {2021},
}