Pach, J.Tomon, I.2019-09-232019-09-232019-09-232019-01-01https://infoscience.epfl.ch/handle/20.500.14299/161446WOS:000484349000098An ordered graph G(<) is a graph with a total ordering < on its vertex set. A monotone path of length k is a sequence of vertices v(1) < v(2) < ... < v(k) such that v(i)v(j) is an edge of G(<) if and only if vertical bar j - i vertical bar = 1. A bi-clique of size m is a complete bipartite graph whose vertex classes are of size m.We prove that for every positive integer k, there exists a constant c(k) > 0 such that every ordered graph on n vertices that does not contain a monotone path of length k as an induced subgraph has a vertex of degree at least c(k)n, or its complement has a bi-clique of size at least c(k)n/log n. A similar result holds for ordered graphs containing no induced ordered subgraph isomorphic to a fixed ordered matching.As a consequence, we give a short combinatorial proof of the following theorem of Fox and Pach. There exists a constant c > 0 such the intersection graph G of any collection of n x-monotone curves in the plane has a bi-clique of size at least cn= log n or its complement contains a bi-clique of size at least cn. (A curve is called x-monotone if every vertical line intersects it in at most one point.) We also prove that if G has at most (1/4 - epsilon) (n 2) edges for some epsilon > 0, then (G) over bar contains a linear sized bi-clique. We show that this statement does not remain true if we replace 1/4 by any larger constants.Mathematicstext::journal::journal article::research article