A characterization of edge-ordered graphs with almost linear extremal functions

Gaurav Kucheriya (Matousek prize lecture)

Charles University

February 29, 2024, 12:20 in S6


The Turán-type extremal graph theory aims to determine the maximum 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 by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos and Vizer. In this talk we show that the extremal functions of edge-ordered forests of order chromatic number 2 is almost linear, whereas the extremal function of any other edge-ordered graph is at least n^c, for some c>1. In other words, we characterize the forbidden edge ordered graphs with almost linear extremal functions.