Paperlane

no. 10 · Friday 6 November 2026

Palettes determine relative Turán densities for ordered graphs

Domagoj Bradač, Lior Gishboliner, Freddie Illingworth, Oliver Janzer, Arjun Ranganathan, Leo Versteegen and Ella Williams

math.CO · v2 · 28 pp

Abstract

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. We show that $ρ_{<}(F)$ is determined by a minimal palette construction for $F$ and give a finite algorithm for computing it exactly. This has many applications: in particular we resolve two problems of Reiher, Rödl, Sales and Schacht and three problems of King et al. Moreover, in the course of the proof we show that $ρ_{<}(F)$ is equal to another natural parameter, namely the uniform Turán density of $F$, which is the infimum $α$ such that every ordered graph with density at least $α$ between any two large intervals contains a copy of $F$.

comments
28 pages
fields
Combinatorics
pdf ↗ page arXiv:2511.21571 ↗