A Study on the Amount of Random Graph Groupies

In 1980, Ajtai, Komlos and Szemer{'e}di defined “groupie”: Let $G=(V,E)$ be a simple graph, $\mathrm{\mid }V\mathrm{\mid }=n$, $\mathrm{\mid }E\mathrm{\mid }=e$. For a vertex $v\in V$, let $r(v)$ denote the sum of the degrees of the vertices adjacent to $v$. We say $v\in V$ is a {\it groupie}, if $\frac{r(v)}{\mathrm{deg}(v)}\ge \frac{e}{n}\mathrm{.}$ In this paper, we prove that in random graph $B(n,p)$, $0<p<1$, the proportion of groupies converges in probability towards $\mathrm{\Phi }(1)\approx 0.8413$ as $n$ approaches infinity, where $\mathrm{\Phi }(x)$ is the distribution function of standard normal distribution N(0,1). We also discuss the asymptotic behavior of the proportion of groupies in complete bipartite graph $B(n_1,n_2,p)$.