Reminder: this is today.
Misha.
----------------------------------------------------------------------
On 2022-03-21 08:23, Mykhaylo Tyomkyn wrote:
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).
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz