Connectivity threshold for superpositions of Bernoulli random graphs. II

2023/11/15 by Bloznelis, Mindaugas, Marma, Dominykas, Vaicekauskas, Rimantas
#05C40 #05C80 #05C82 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2311.09317

Abstract

Let G₁,…, G_m be independent Bernoulli random subgraphs of the complete graph \cal K_n having variable sizes X₁,…, X_m∈ \0,1,2,…\ and densities Q₁,…, Q_m∈ [0,1]. Letting n,m→+∞ we establish the connectivity threshold for the union ∪_i=1^mG_i defined on the vertex set of \cal K_n. Assuming that (X₁,Q₁), (X₂,Q₂),…, (X_m,Q_m) are independent identically distributed bivariate random variables and ln n -(m)/(n)E(X₁(1-(1-Q₁)^|X₁-1|)→ c we show that P\∪_i=1^mG_i is connected\→ e^-ec.The result extends to the case of non-identically distributed random variables (X₁,Q₁),…, (X_m,Q_m) as well.

Related

• Connectivity threshold for superpositions of Bernoulli random graphs
• k-connectivity threshold for superpositions of Bernoulli random graphs
• Connectivity Threshold for random subgraphs of the Hamming graph
• On Connectivity in Random Graph Models with Limited Dependencies
• Clustering and percolation on superpositions of Bernoulli random graphs