4.3 Article

On the Turan number of ordered forests

期刊

JOURNAL OF COMBINATORIAL THEORY SERIES A
卷 165, 期 -, 页码 32-43

出版社

ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcta.2019.01.006

关键词

Turan problem; Ordered forest; Forbidden submatrix

资金

  1. SNSF [200020-162884, 200021-175977]
  2. Lendulet project of the Hungarian Academy of Sciences
  3. National Research, Development and Innovation Office, NKFIH [K-116769, SNN-117879]

向作者/读者索取更多资源

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.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据