Lutz Warnke “Counting extensions in random graphs”

September 10, 2020
19.00 MSK (UTC +3)

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.

The talk will be held in zoom
Meeting ID: 279-059-822
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii ( or to Maksim Zhukovskii ( if you want to be added to mailing list.


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.