How to determine if a random graph with a fixed degree sequence has a giant component

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

Abstract

For a fixed degree sequence D = (d1, ..., dn), let G(D) be a uniformly chosen (simple) graph on {1, ..., n} where the vertex i has degree di. In this paper we determine whether G(D) has a giant component with high probability, essentially imposing no conditions on D. We simply insist that the sum of the degrees in D which are not 2 is at least λ(n) for some function λ going to infinity with n. This is a relatively minor technical condition, and when D does not satisfy it, both the probability that G(D) has a giant component and the probability that G(D) has no giant component are bounded away from 1.

Details

Original languageEnglish
Pages (from-to)263-310
Number of pages48
JournalProbability Theory and Related Fields
Volume170
Issue number1-2
Early online date26 Jan 2017
Publication statusPublished - Feb 2018