Discrete Math Seminar continues this week with Dylan King from Caltech telling us about Relative Ordered Tur\’an Densities (abstract below).
Abstract:
The Tur\’an density of a forbidden graph F, \pi(F), is the largest edge density in a host graph H which contains no copy of F, and a well-known Theorem of Erd\H{o}s, Stone, and Simonovits determines \pi(F) as a function of the chromatic number \chi(F). The relative Tur\’an density of a forbidden graph F, \rho(F), is the largest \alpha so that every host graph H contains an F-free subgraph H’ with e(H’) \geq \alpha e(H). A naïve random algorithm shows that, in fact, \pi(F) = \rho(F).
In the setting of ordered graphs (where the vertex set is equipped with a total ordering <), Tur\’an problems were studied systematically by Pach and Tardos, who gave a formula for the ordered Tur\’an density of F using the interval chromatic number. In 2025, Reiher, R\”{o}dl, Sales, and Schacht observed that, for ordered graphs, \pi and \rho no longer necessarily coincide and initiated a formal study of the latter, determining the relative ordered Tur\’an density \rho of the monotone path of length \ell. In this talk we will (after introducing \rho) describe some further progress on describing this parameter.
Joint work with Bernard Lidick\’{y}, Minghui Ouyang, Florian Pfender, Runze Wang, and Zimu Xiang at the 2025 GRWC.