Connectivity of inhomogeneous random graphs

2012/10/23 by Devroye, Luc, Fraiman, Nicolas · 2 citations
#05C80 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1210.6259

Abstract

We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p = c log n/n. We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i,j) is added with probability min(1, \K(X_i,X_j) log n/n), where \K ≥ 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined.

Cited by

• Inhomogeneous random 2-SAT
• Gaussian fluctuations of generalized U-statistics and subgraph counting in the binomial random-connection model

Related

• Connectivity of inhomogeneous random graphs II
• The connectivity and phase transition in inhomogeneous random graphs of finite types
• Connectivity of Poissonian Inhomogeneous random Multigraphs
• Exponential bounds for inhomogeneous random graphs in a Gaussian case
• Connectivity Threshold for random subgraphs of the Hamming graph