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

Abstract

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 in distribution to a random variable having the standard Gumbel distribution.

Cited by in corpus (1)

• Analytical results for the distribution of cover times of random walks on random regular graphs