An ordered graph $H$ is a simple graph with a linear order on its vertex set. The corresponding Tur\'an problem, first studied by Pach and Tardos, asks for the maximum number $\text{ ex}_<(n,H)$ of edges in an ordered graph on $n$ vertices that does not contain $H$ as an ordered subgraph. It is known that $\text{ ex}_<(n,H) > n^{ 1+\varepsilon}$ for some positive $\varepsilon=\varepsilon(H)$ unless $H$ is a forest that has a proper 2-coloring with one color class totally preceding the other one. Making progress towards a conjecture of Pach and Tardos, we prove that $\text{ ex}_<(n,H) =n^{ 1+o(1)}$ holds for all such forests that are "degenerate" in a certain sense. This class includes every forest for which an $n^{ 1+o(1)}$ upper bound was previously known, as well as new examples. Our proof is based on a density-increment argument.
Categories: math.CO