  An 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<\ldots<v_k$ such that $v_iv_{j}$ is an edge of $G_<$ if and only if
$|j-i|=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_kn$, or its complement has a bi-clique of size at least $c_kn/\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
$\left(\frac14 -\epsilon\right){n\choose 2}$ edges for some $\epsilon>0$, then
$\overline{G}$ contains a linear sized bi-clique. We show that this statement
does not remain true if we replace $\frac14$ by any larger constants.

Combinatorics