## Abstract

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and 1/2m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X_{1},..., X_{n})|∑ X_{1} = m}, where X_{1},..., X_{n} are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p = p(n), the distribution of the degree sequence can be approximated by {(X_{1},..., X_{n})|∑ X_{1} is even}, where X_{1},..., X_{n} are independent random variables each having the distribution Binom (n - 1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^{-k} for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t = t(n) as n → ∞.

Original language | English |
---|---|

Pages (from-to) | 97-117 |

Number of pages | 21 |

Journal | Random Structures & Algorithms |

Volume | 11 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1997 |

Externally published | Yes |