On the Turan number of ordered forests

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:165

Article

Korandi, Daniel¹  Tardos, Gabor²  Tomon, Istvan¹  Weidert, Craig³ 

[1] Ecole Polytech Fed Lausanne, Inst Math, Lausanne, Switzerland

[2] Renyi Inst, Budapest, Hungary

[3] Simon Fraser Univ, Burnaby, BC, Canada

关键词: Turan problem;    Ordered forest;    Forbidden submatrix;   

DOI  :  10.1016/j.jcta.2019.01.006

来源: Elsevier

【 摘 要 】

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan 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) > n(1+epsilon) for some positive epsilon = epsilon(H) unless H is a forest that has a proper 2-coloring with one color class totally preceding the other one. Making progress towards a conjecture of Pach and Tardos, we prove that ex(<) (n, H) = n(1+o(1)) holds for all such forests that are degenerate in a certain sense. This class includes every forest for which an n(1+o(1)) upper bound was previously known, as well as new examples. Our proof is based on a density-increment argument. (C) 2019 Elsevier Inc. All rights reserved.

【 授权许可】

Free