The probability that a random multigraph is simple
From MaRDI portal
Abstract: Consider a random multigraph G* with given vertex degrees d_1,...,d_n, contructed by the configuration model. We show that, asymptotically for a sequence of such multigraphs with the number of edges (d_1+...+d_n)/2 tending to infinity, the probability that the multigraph is simple stays away from 0 if and only if sum d_i^2=O(sum d_i). This was previously known only under extra assumtions on the maximum degree. We also give an asymptotic formula for this probability, extending previous results by several authors.
Recommendations
Cites work
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A simple solution to the k‐core problem
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Probability: A Graduate Course
- The asymptotic distribution of short cycles in random regular graphs
- The asymptotic number of labeled graphs with given degree sequences
- The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
- Uniform generation of random regular graphs of moderate degree
Cited in
(94)- Mixing times of random walks on dynamic configuration models
- The tail does not determine the size of the giant
- Size biased couplings and the spectral gap for random regular graphs
- Replica bounds by combinatorial interpolation for diluted spin systems
- A network with tunable clustering, degree correlation and degree distribution, and an epidemic thereon
- First passage percolation on random graphs with finite mean degrees
- Geometry of the minimal spanning tree of a random 3-regular graph
- Multiplexity analysis of networks using multigraph representations
- Global lower mass-bound for critical configuration models in the heavy-tailed regime
- Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
- Epidemic spreading and equilibrium social distancing in heterogeneous networks
- Rare event asymptotics for exploration processes for random graphs
- Chase-escape on the configuration model
- Universality for critical heavy-tailed network models: metric structure of maximal components
- The median of the number of simple paths on three vertices in the random graph
- Heavy-tailed configuration models at criticality
- Survival and extinction of epidemics on random graphs with general degree
- Optimal subgraph structures in scale-free configuration models
- Central limit theorems for SIR epidemics and percolation on configuration model random graphs
- Bootstrap percolation in directed inhomogeneous random graphs
- Estimating graph parameters with random walks
- Limit laws for self-loops and multiple edges in the configuration model
- Degree distribution dynamics for disease spreading with individual awareness
- Degree distribution of shortest path trees and bias of network sampling algorithms
- Limit distributions of the number of loops in a random configuration graph
- Applications of the variance of final outbreak size for disease spreading in networks
- The densest subgraph problem in sparse random graphs
- Making multigraphs simple by a sequence of double edge swaps
- The diameter of the directed configuration model
- Joint distribution of distances in large random regular networks
- Distribution dynamics for SIS model on random networks
- The scaling window for a random graph with a given degree sequence
- How Clustering Affects Epidemics in Random Networks
- The first-order contiguity of sparse random graphs with prescribed degrees
- Push is Fast on Sparse Random Graphs
- Asymptotic equivalence and contiguity of some random graphs
- Random graphs with forbidden vertex degrees
- SIR epidemics on random graphs with a fixed degree sequence
- A simple solution to the k‐core problem
- The degree distribution of the random multigraphs
- Exponential Random Graphs as Models of Overlay Networks
- Threshold behaviour and final outcome of an epidemic on a random network with household structure
- scientific article; zbMATH DE number 56470 (Why is no real title available?)
- Diffusion and cascading behavior in random networks
- Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism
- The construction and properties of assortative configuration graphs
- Optimal connectivity for a large financial network
- The component sizes of a critical random graph with given degree sequence
- scientific article; zbMATH DE number 867655 (Why is no real title available?)
- Characterizing optimal sampling of binary contingency tables via the configuration model
- Analyzing local and global properties of multigraphs
- Managing Default Contagion in Inhomogeneous Financial Networks
- Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees
- Limit theorems for assortativity and clustering in null models for scale-free networks
- Glauber dynamics for Ising models on random regular graphs: cut-off and metastability
- The giant component of the directed configuration model revisited
- Critical value asymptotics for the contact process on random graphs
- A Dynamic Contagion Risk Model with Recovery Features
- Random graphs with given vertex degrees and switchings
- Asymptotic normality in random graphs with given vertex degrees
- Near-critical SIR epidemic on a random graph with given degrees
- Component structure of the configuration model: barely supercritical case
- The front of the epidemic spread and first passage percolation
- The probability that a random multigraph is simple. II
- Law of large numbers for the SIR epidemic on a random graph with given degrees
- The interpolation method for random graphs with prescribed degrees
- Critical window for connectivity in the configuration model
- Diameter in ultra-small scale-free random graphs
- Graphs with specified degree distributions, simple epidemics, and local vaccination strategies
- The Threshold of Symmetry in Random Graphs with Specified Degree Sequences
- Epidemics on networks with preventive rewiring
- Bootstrap percolation in living neural networks
- Contagion risks and security investment in directed networks
- Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph
- Largest component of subcritical random graphs with given degree sequence
- scientific article; zbMATH DE number 7731163 (Why is no real title available?)
- Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
- Rankings in directed configuration models with heavy tailed in-degrees
- Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
- A note on the Markovian SIR epidemic on a random graph with given degrees
- Connectivity of random hypergraphs with a given hyperedge size distribution
- Connectivity of random graphs after centrality-based vertex removal
- Subcritical epidemics on random graphs
- Minimum stationary values of sparse random directed graphs
- The full rank condition for sparse random matrices
- Randomized algorithms to generate hypergraphs with given degree sequences
- Convergence of the height process of supercritical Galton-Watson forests with an application to the configuration model in the critical window
- Asymptotic optimality of degree-greedy discovering of independent sets in configuration model graphs
- The second phase transition of the contact process on a random regular graph
- Counting triangles in power-law uniform random graphs
- SIR dynamics with vaccination in a large configuration model
- Enumeration of graphs with a heavy-tailed degree sequence
- The configuration model for partially directed graphs
- The largest component in a subcritical random graph with a power law degree distribution
This page was built for publication: The probability that a random multigraph is simple
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557510)
