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 c=c(k)>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^c. This strengthens a theorem of Bousquet, Lagoutte, and Thomasse, who proved the analogous statement for unordered graphs.

Joint work with Istvan Tomon.