The connectivity threshold conjecture for uniform random intersection graphs

About 18 years old · traced to

Let G(n,m,k)G(n,m,k) be the random intersection graph on nn vertices in which each vertex is assigned a uniformly random kk-subset of a colour set of size mm, with two vertices adjacent when their assigned colour sets intersect. Let kk and mm be functions of nn, and let ω→∞\omega\to\infty as n→∞n\to\infty.

Connectivity threshold conjecture.

(i) If

k2nm=log⁡n+ω,\frac{k^2n}{m}=\log n+\omega,

then almost surely G(n,m,k)G(n,m,k) is connected. (ii) If

k2nm=log⁡n−ω,\frac{k^2n}{m}=\log n-\omega,

then almost surely G(n,m,k)G(n,m,k) is not connected.

This conjecture predicts a sharp connectivity threshold for uniform random intersection graphs at k2n/m=log⁡nk^2n/m=\log n.

References

Primary source

Simon R. Blackburn and Stefanie Gerke, “Connectivity of the Uniform Random Intersection Graph”, arXiv:0805.2814 (2008).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.