The distribution of the maximum number of common neighbors in the random graph

Igor Rodionov, Maksim Zhukovskii

Let ${\Delta }_{k;n}$ be the maximum number of common neighbors of a set of $k$ vertices in $G(n,p)$. In this paper, we find $a_n$ and ${\sigma }_n$ such that $\frac{{\Delta }_{k;n}-a_n}{{\sigma }_n}$ converges i…