Characterization of edge-ordered graph with nearly linear extremal functions

The Turán-type extremal theory of graphs asks for the maximal number ex(n,H) of edges in an n-vertex simple graph without containing the forbidden subgraph H. Here ex(n,H) is also called the extremal function of the forbidden subgraph H.

This classical theory has been extended in many directions. A pretty recent such extension is to edge ordered graphs. These are simple graphs with a linear order on their edges. The extremal function ex_<(n,H) of a forbidden edge ordered graph H is is the maximal number of edges in an edge ordered graph that does not contain H as a subgraph WITH THE GIVEN EDGE ORDER. We started to develop this theory with D. Gerbner, A. Methuku, D. Nagy, D. Pálvölgyi and M. Vizer (2020+).

In this talk I will concentrate on a single result generalizing the trivial observation that the Turán-type extremal function of any forbidden forest is linear and 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. Note that a similar characterization is also conjectured for vertex ordered graphs, but that conjecture remains open despite promising partial results.

The result is joint with Gaurav Kucheriya (Charles University)