The maximum degree of a random graph (Q2711619)

Let \(G\) be a random graph from the standard model \(G(n,p)\). Thus \(G\) has \(n\) vertices in which each possible edge appears independently with probability \(p\) (\(0< p< 1\), \(q= 1-p\)). Let \(\phi\) and \(\Phi\) denote the standard normal density and distribution functions, respectively. The main result of this paper is as follows:NEWLINENEWLINENEWLINEFor a random graph \(G\) from \(G^*(n,p)\), let \(p_n= P[\max d(G)\leq np +b\sqrt{npq}]\), where \(b\) is fixed. Then we have \(p^{{1\over n}}_n\to c\) as \(n\to\infty\); where \(c\) is a constant independent of \(p\) and depending only on \(b\) and is given by \(c= \max_\theta[\Phi(b+ \theta)\text{Exp}(-{\theta^2\over 2})]\). The above maximum is attained (uniquely) at \(\theta_0= \theta_0(b)\), the root of the equation \(\theta_0\Phi(b+ \theta_0)= \phi(b+\theta)\). For \(p={1\over 2}\) and \(b=0\), we have \(\theta_0= 0.506\dots\) and \(c= 0.6102\dots\)\ .NEWLINENEWLINENEWLINEThe proof presented here is based on considering the complete graph \(K_n\) with weights on the edges, and taking these weights as independent normal \(N(p,pq)\) random variables giving a continuous approximation to \(G^*(n,p)\).