Georgia Institute of Technology College of Sciences

We consider rooted subgraph extension counts, such as (a) the number of triangles containinga given vertex, or (b) the number of paths of length three connecting two given 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. Perhaps surprisingly, the question whether these conditions are necessary has remained open. In this talk we briefly discuss our qualitative solution of this problem for the `strictly balanced' case, and mention several intriguing questions that remain open (which lie at the intersection of probability theory + discrete mathematics, and are of concentration inequality type). Based on joint work in progress with Matas Sileikis