





















Reiher, Rödl, Sales, and Schacht initiated the study of relative Turán densities of ordered graphs and showed that it is more subtle and interesting than the unordered case. For an ordered graph $F$, its relative Turán density, $ρ_{<}(F)$, is the greatest $α$ such that every ordered graph $G$ has an $F$-free subgraph with at least $αe(G)$ edges. This paper contains two main results about relative Turán densities. First, we find a family of host graphs that is optimal for all $F$. Second, we characterise the ordered graphs with zero relative Turán density: precisely those with no monotone path of length two.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。