Lutz Warnke "Counting extensions in random graphs"
Lutz Warnke from Georgia Institute of Technology will give the talk "Counting extensions in random graphs" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.
Abstract:
We consider rooted subgraphs in random graphs, i.e., extension counts such as (a) the number of triangles containing a given `root' vertex, or (b) the number of paths of length three connecting two given `root' vertices. In 1989 Spencer gave sufficient conditions for the event that, whp, all roots of the binomial random graph G(n,p) have the same asymptotic number of extensions, i.e., $(1 \pm \epsilon)$ times their expected number. For the important strictly balanced case, Spencer also raised the fundamental question whether these conditions are necessary.
We answer this question by a careful second moment argument, and discuss some open problems and cautionary examples for the general case.
Based on joint work with Matas Sileikis, see arXiv:1911.03012
Watch the video:
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.