The connectivity threshold conjecture for uniform random intersection graphs
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 .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.