Critical window for connectivity in the configuration model

DOI10.1017/S0963548317000177MaRDI QIDQ5366967zbMATH OpenFDO

Authors Lorenzo Federico, Remco van der Hofstad

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic probabilityconnectivity probability

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Enumeration in graph theory (05C30) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We identify the asymptotic probability of a configuration model $$ to produce a connected graph within its critical window for connectivity that is identified by the number of vertices of degree 1 and 2, as well as the expected degree. In this window, the probability that the graph is connected converges to a non-trivial value, and the size of the complement of the giant component weakly converges to a finite random variable. Under a finite second moment condition we also derive the asymptotics of the connectivity probability conditioned on simplicity, from which the asymptotic number of simple connected graphs with a prescribed degree sequence follows.

Recommendations

• On the connectivity of configuration graphs
• Critical window for the configuration model: finite third moment degrees
• Heavy-tailed configuration models at criticality
• scientific article; zbMATH DE number 15665
• When are random graphs connected

Cites work

• A critical point for random graphs with a given degree sequence
• A new approach to the giant component problem
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 747040 (Why is no real title available?)
• Paths in graphs
• Random graphs and complex networks. Volume 1
• The asymptotic connectivity of labelled regular graphs
• The largest component in a subcritical random graph with a power law degree distribution
• The probability that a random multigraph is simple
• The probability that a random multigraph is simple. II
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Tutorial on large deviations for the binomial distribution

Cited in

(16)

• Mixing times of random walks on dynamic configuration models
• When is a scale-free graph ultra-small?
• Tight fluctuations of weight-distances in random graphs with infinite-variance degrees
• The parabolic Anderson model on a Galton-Watson tree
• On the connectivity of configuration graphs
• Limit theorems for assortativity and clustering in null models for scale-free networks
• Critical window for the vacant set left by random walk on the configuration model
• The Threshold of Symmetry in Random Graphs with Specified Degree Sequences
• On the modularity of 3‐regular random graphs and random graphs with given degree sequences
• Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
• Connectivity of Poissonian inhomogeneous random multigraphs
• scientific article; zbMATH DE number 7731163 (Why is no real title available?)
• New approximations for network reliability
• Building a random network with a given expected giant component
• Universal `winner-takes-it-all' phenomenon in scale-free random graphs
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks

This page was built for publication: Critical window for connectivity in the configuration model

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