Dear all,
This week's speaker is Gaurav Kucheriya (Charles University). Please find the talk details below.
Best regards, Misha Tyomkyn.
-------------------------------------------------------------------
Characterization of edge-ordered graphs with nearly linear extremal functions.
Gaurav Kucheriya Charles University March 24, 2022, 12:20 in S6
Abstract 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).
--------------------------------------------------------------------