Small subgraph counts in random graphs: a survey

Combinatorics Seminar
Friday, October 6, 2017 - 15:00
1 hour (actually 50 minutes)
Skiles 005
Charles University Prague
Given a (fixed) graph H, let X be the number of copies of H in the random binomial graph G(n,p). In this talk we recall the results on the asymptotic behaviour of X, as the number n of vertices grows and pis allowed to depend on. In particular we will focus on the problem of estimating probability that X is significantly larger than its expectation, which earned the name of the 'infamous upper tail'.