# 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.