On Relative Ordered Turán Density

Abstract

For an ordered graph $F$, denote the Turán density by $\vec{\ddot{I}}€(F)$. The relative Turán density, denoted by $\ddot{I}(F)$, is the supremum over $\hat{I}\pm \in [0,1]$ such that every ordered graph $G$ contains an $F$-free subgraph $G^{\prime }$ with $e(G^{\prime })\ge \hat{I}\pm e(G)$. Reiher, Rödl, Sales and Schacht showed that $\ddot{I}(P)=\vec{\ddot{I}}€(P)/2$ and $\ddot{I}(K)=\vec{\ddot{I}}€(K)$ for any ascending path $P$ or clique $K$. They asked if there are any ordered graphs $F$ with $\vec{\ddot{I}}€(F)/2<\ddot{I}(F)<\vec{\ddot{I}}€(F)$. We answer this question in the affirmative by describing a family of such $F$. We also show that the relative Turán densities of a large family of ordered matchings (including $\{\{1,6\},\{2,3\},\{4,5\}\}$ and $\{\{1,3\},\{2,5\},\{4,6\}\}$) are $0$.

14 pages, 4 figures