On the Turán number of ordered forests

Abstract

An ordered graph $H$ is a simple graph with a linear order on its vertex set. The corresponding Turán 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+\epsilon }$ for some positive $\epsilon =\epsilon (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.

10 pages