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.
Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.
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 -