Name
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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.jcta.2019.01.006 | Journal of Combinatorial Theory, Series A |
Keywords | DocType | Volume |
Turán problem,Ordered forest,Forbidden submatrix | Journal | 165 |
ISSN | Citations | PageRank |
0097-3165 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Korándi | 1 | 2 | 3.45 |
| Gábor Tardos | 2 | 1261 | 140.58 |
| István Tomon | 3 | 0 | 0.34 |
| Craig Weidert | 4 | 0 | 0.34 |