A reminder: this is today
------------------------------------------------------
On 2024-02-26 09:20, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 29 February: a prize lecture given by Gaurav Kucheriya, one of the three winners of the Jirka Matousek prize 2023. Please find the talk details below.
Best regards, Misha Tyomkyn.
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
Abstract 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.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz