Random graphs with given vertex degrees and switchings

DOI10.1002/RSA.20911MaRDI QIDQ5120739zbMATH OpenOpenAlexFDO

Authors Svante Janson

Publication date 16 September 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.09744

zbMATH Keywords

asymptotic normalityconfiguration modelcontiguityrandom graphsswitchings

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

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.

Recommendations

• Asymptotic normality in random graphs with given vertex degrees
• Generating simple random graphs with prescribed degree distribution
• The probability that a random multigraph is simple
• The probability that a random multigraph is simple. II
• Directed random graphs with given degree distributions

Cites work

• A critical point for random graphs with a given degree sequence
• A new approach to the giant component problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• An old approach to the giant component problem
• Asymptotic equivalence and contiguity of some random graphs
• Asymptotic normality in random graphs with given vertex degrees
• Asymptotic normality of the \(k\)-core in random graphs
• Central limit theorems in the configuration model
• Component structure of the configuration model: barely supercritical case
• Enumeration of graphs with a heavy-tailed degree sequence
• Generating random regular graphs
• Generating simple random graphs with prescribed degree distribution
• How to determine if a random graph with a fixed degree sequence has a giant component
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• On the Chromatic Number of Random Graphs with a Fixed Degree Sequence
• Probability: a graduate course
• Random graphs and complex networks. Volume 1
• The asymptotic distribution of short cycles in random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• The asymptotic variance of the giant component of configuration model random graphs
• The phase transition in the configuration model
• The probability that a random multigraph is simple
• The probability that a random multigraph is simple. II
• The scaling window for a random graph with a given degree sequence
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Uniform generation of random graphs with power-law degree sequences
• Uniform generation of random regular graphs
• Uniform generation of random regular graphs of moderate degree

Cited in

(10)

• Central limit theorems for SIR epidemics and percolation on configuration model random graphs
• Making multigraphs simple by a sequence of double edge swaps
• Central limit theorem for statistics of subcritical configuration models
• Random Seidel switching on graphs
• scientific article; zbMATH DE number 7535774 (Why is no real title available?)
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Self-similarity of communities of the ABCD model
• Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
• A central limit theorem for the matching number of a sparse random graph

This page was built for publication: Random graphs with given vertex degrees and switchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120739)