On the Turán number of ordered forests

Korándi, Dániel and Tardos, Gábor and Tomon, István and Weidert, Craig (2017) On the Turán number of ordered forests. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 61. pp. 773-779. ISSN 1571-0653

Preview

Text 1711.07723v1.pdf Download (160kB) | Preview

Abstract

An ordered graph H is a graph with a linear ordering on its vertex set. The corresponding Turán problem, first studied by Pach and Tardos, asks for the maximum number ex<(n,H) of edges in an ordered graph on n vertices that does not contain H as an ordered subgraph. It is known that ex<(n,H)>n1+ε for some positive ε=ε(H) unless H is a forest that has a bipartition V1∪V2 such that V1 totally precedes V2 in the ordering. Making progress towards a conjecture of Pach and Tardos, we prove that ex<(n,H)=n1+o(1) holds for all such forests that are “degenerate” in a certain sense. This class includes every forest for which an n1+o(1) upper bound was previously known, as well as new examples. For example, the class contains all forests with |V1|≤3. Our proof is based on a density-increment argument. © 2017 Elsevier B.V.

Actions (login required)

Edit Item