The connectivity threshold conjecture for uniform random intersection graphs

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 nn\to\infty.

Connectivity threshold conjecture.

(i) If

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

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

k2nm=lognω,\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=lognk^2n/m=\log n.

Sources & referencesView supporting material

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.