The conjectured sharp threshold for connectivity and Hamiltonicity in random intersection graphs

Let α<1\alpha<1, let

p=lnn+ωm,p=\frac{\ln n+\omega}{m},

and suppose that ω\omega\to\infty. Then, with high probability, the random intersection graph G(n,m,p)\mathcal{G}(n,m,p) is kk-connected for any constant kk and contains a Hamilton cycle.

Connectivity and Hamiltonicity conjecture. Under these assumptions, G(n,m,p)\mathcal{G}(n,m,p) is kk-connected for every fixed constant kk 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 α<1\alpha<1. 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

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.