Pach, JanosTomon, Istvan2019-09-262019-09-262019-09-262019-12-0110.1016/j.ejc.2019.07.005https://infoscience.epfl.ch/handle/20.500.14299/161549WOS:000485210100005An ordered graph G(<) is a graph with a total ordering < on its vertex set. A monotone path of length k - 1 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. (C) 2019 Elsevier Ltd. All rights reserved.Mathematicstext::journal::journal article::research article