## Abstract

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).

Original language | English (US) |
---|---|

Pages (from-to) | 324-338 |

Number of pages | 15 |

Journal | Discrete and Computational Geometry |

Volume | 64 |

Issue number | 2 |

DOIs | |

State | Published - Sep 1 2020 |

## Keywords

- Convex geometric graphs
- Ordered graphs
- Turán number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics