On the Turán number of ordered forests
Dániel Korándi, Gábor Tardos, István Tomon, Craig Weidert · arXiv (Cornell University) · 2017
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^{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}_