2025/08/07 by King, Dylan, Lidický, Bernard, Ouyang, Minghui +3 · 1 citation
#05C35 (primary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.05515
For an ordered graph F, denote the Turán density by π(F). The relative Turán density, denoted by ρ(F), is the supremum over α∈ [0,1] such that every ordered graph G contains an F-free subgraph G' with e(G') ≥ αe(G). Reiher, Rödl, Sales and Schacht showed that ρ(P) = π(P)/2 and ρ(K) = π(K) for any ascending path P or clique K. They asked if there are any ordered graphs F with π(F)/2 < ρ(F) < π(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.