Ordered and Convex Geometric Trees with Linear Extremal Function

Zoltán Füredi, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)324-338
Number of pages15
JournalDiscrete and Computational Geometry
Volume64
Issue number2
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Ordered and Convex Geometric Trees with Linear Extremal Function'. Together they form a unique fingerprint.

Cite this