A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions

The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. (Turán problems for Edge-ordered graphs, 2021). They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are n¹⁺ᵒ⁽¹⁾ n 1 + o ( 1 ) . Here we resolve this conjecture proving the stronger upper bound of n2O(√log n) n 2 O ( log n ) . This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions Ω (nᶜ) Ω ( n c ) for some $$c>1$$ c > 1 . However, our result is probably not the last word: here we conjecture that the even stronger upper bound of nlog O(1)n n log O ( 1 ) n also holds for the same set of extremal functions.