Ordered and Convex Geometric Trees with Linear Extremal Function

The extremal functions ex _→(n, F) and ex _↻(n, F) for ordered and convex geometric acyclic graphs F have been extensively investigated by a number of researchers. Basic questions are to determine when ex _→(n, F) and ex _↻(n, F) are linear in n, the latter posed by Brass–Károlyi–Valtr in 2003. In this paper, we answer both these questions for every tree F. We give a forbidden subgraph characterization for a family T of ordered trees with k edges, and show that ex→(n,T)=(k-1)n-(k2) for all n≥ k+ 1 when T∈ T and ex _→(n, T) = Ω (nlog n) for T∉ T. We also describe the family T^′ of the convex geometric trees with linear Turán number and show that for every convex geometric tree F∉ T^′, ex _↻(n, F) = Ω (nlog log n).