The conjectured sharp threshold for connectivity and Hamiltonicity in random intersection graphs
The conjectured sharp threshold for connectivity and Hamiltonicity in random intersection graphs
Let , let
and suppose that . Then, with high probability, the random intersection graph is -connected for any constant and contains a Hamilton cycle.
Connectivity and Hamiltonicity conjecture. Under these assumptions, is -connected for every fixed constant and contains a Hamilton cycle with high probability.
The conjecture is motivated by the minimum-degree phenomenon and proposes a tightening of the threshold function in the cited theorem for the case . The supplied text gives no resolution of this conjecture.
Sources & referencesView supporting material
Primary source
Katarzyna Rybarczyk, “Sharp threshold functions for the random intersection graph via coupling method?”, arXiv:0910.0749 (2009).
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.