We consider a generalization of the maximum degree in random graphs. Given a rooted tree $T$, let $X_v$ denote the number of copies of T rooted at v in the binomial random graph $G_{n,p}$. We ask the question where the maximum $M_n = max \{X_1, ..., X_n\}$ of $X_v$ over all vertices is concentrated. For edge-probabilities $p=p(n)$ tending to zero not too fast, the maximum is asymptotically attained by the vertex of maximum degree. However, for smaller edge probabilities $p=p(n)$, the behavior is more complicated: our large deviation type optimization arguments reveal that the behavior of $M_n$ changes as we vary $p=p(n)$, due to different mechanisms that can make the maximum large.

Based on joint work with Pedro Araújo, Simon Griffiths and Matas Šileikis; see arXiv:2310.11661