Korándi, Dániel and Tardos, Gábor and Tomon, István and Weidert, Craig (2019) On the Turán number of ordered forests. JOURNAL OF COMBINATORIAL THEORY SERIES A, 165. pp. 32-43. ISSN 0097-3165
|
Text
1711.07723v1.pdf Download (160kB) | Preview |
Abstract
An ordered graph H is a simple graph with a linear order 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 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)=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. Our proof is based on a density-increment argument. © 2019 Elsevier Inc.
| Item Type: | Article |
|---|---|
| Additional Information: | Institute of Mathematics, EPFL, Lausanne, Switzerland Rényi Institute, Budapest, Hungary Simon Fraser University, Burnaby, Canada Export Date: 1 October 2019 CODEN: JCBTA Institute of Mathematics, EPFL, Lausanne, Switzerland Rényi Institute, Budapest, Hungary Simon Fraser University, Burnaby, Canada Export Date: 2 October 2019 CODEN: JCBTA |
| Uncontrolled Keywords: | Forbidden submatrix; Turán problem; Ordered forest; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA71 Number theory / számelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 02 Oct 2019 13:44 |
| Last Modified: | 02 Oct 2019 13:44 |
| URI: | http://real.mtak.hu/id/eprint/101924 |
Actions (login required)
 |
Edit Item |
