The connectivity threshold conjecture for uniform random intersection graphs
Let be the random intersection graph on vertices in which each vertex is assigned a uniformly random -subset of a colour set of size , with two vertices adjacent when their assigned colour sets intersect. Let and be functions of , and let as .
Connectivity threshold conjecture.
(i) If
then almost surely is connected. (ii) If
then almost surely is not connected.
This conjecture predicts a sharp connectivity threshold for uniform random intersection graphs at .
References
Primary source
Simon R. Blackburn and Stefanie Gerke, “Connectivity of the Uniform Random Intersection Graph”, arXiv:0805.2814 (2008).
Progress summary
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.