Characterization of edge-ordered graphs with nearly linear extremal functions.

The Turán-type extremal theory of graphs asks for the maximal number of edges in a simple graph without containing the forbidden subgraph H. Recently this problem has been studied for edge-ordered graphs which are simple graphs with a linear order on their edges.

In this talk we concentrate on a single result generalizing the simple observation that the Turán-type extremal function of any forbidden forest is linear but the extremal function of a forbidden simple graph with a cycle is much larger. We characterize the forbidden edge ordered graphs with almost linear extremal functions.

This is joint work with Gábor Tardos (Alfréd Rényi Institute of Mathematics).