TY - JOUR

T1 - Ordered and Convex Geometric Trees with Linear Extremal Function

AU - Füredi, Zoltán

AU - Kostochka, Alexandr

AU - Mubayi, Dhruv

AU - Verstraëte, Jacques

N1 - Funding Information:
This research was partly conducted during AIM SQuaRes (Structured Quartet Research Ensembles) workshops, and we gratefully acknowledge the support of AIM. We also thank the referees for their comments. Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

PY - 2020/9/1

Y1 - 2020/9/1

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

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

KW - Convex geometric graphs

KW - Ordered graphs

KW - Turán number

UR - http://www.scopus.com/inward/record.url?scp=85074823463&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074823463&partnerID=8YFLogxK

U2 - 10.1007/s00454-019-00149-z

DO - 10.1007/s00454-019-00149-z

M3 - Article

AN - SCOPUS:85074823463

VL - 64

SP - 324

EP - 338

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 2

ER -