CMSA : The longest induced path in a sparse random graph

CMSA EVENTS

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

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: https://harvard.zoom.us/j/99715031954?pwd=eVRvbERvUWtOWU9Vc3M2bjN3VndBQT09

Password: 1251442