Random graphs with given vertex degrees and switchings. Issue 1 (13th February 2020)

• Record Type: Journal Article
• Authors: Janson, Svante
• Is Part Of: Random structures & algorithms. Volume 57:Issue 1(2020)
• Page Start: 3
• Page End: 31
• Publication Date: 2020-02-13
• Subjects: random graphs -- configuration model -- switchings -- asymptotic normality -- contiguity; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20911
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Random graphs with a given degree sequence are often constructed using the configuration model, which yields a random multigraph. We may adjust this multigraph by a sequence of switchings, eventually yielding a simple graph. We show that, assuming essentially a bounded second moment of the degree distribution, this construction with the simplest types of switchings yields a simple random graph with an almost uniform distribution, in the sense that the total variation distance is o (1). This construction can be used to transfer results on distributional convergence from the configuration model multigraph to the uniform random simple graph with the given vertex degrees. As examples, we give a few applications to asymptotic normality. We show also a weaker result yielding contiguity when the maximum degree is too large for the main theorem to hold.