CMSA : The longest induced path in a sparse random graph


View Calendar
December 14, 2021 9:30 am - 10:30 am

Stefan Glock - ETH Zurich

A long-standing problem in random graph theory has been to determine asymptotically the length of a longest induced path in sparse random graphs. Independent work of {\L}uczak and Suen from the 90s showed the existence of an induced path of roughly half the optimal size, which seems to be a barrier for certain natural approaches. Recently, in joint work with Dragani\'c and Krivelevich, we solved this problem. In the talk, I will discuss the history of the problem and give an overview of the proof.

Zoom link:

Password: 1251442