Bollobás–Thomason threshold conjecture for binomial random multigraphs

At least 2 years old · documented by

Let k≥3k\ge 3 be fixed, and let P\mathcal{P} be a non-trivial monotone increasing (multi)graph property. A threshold in G(n,p ; ([n]k))\mathbb{G}(n,p\,; \,\binom{[n]}{k}) is a sequence {cn∗}n\{c_n^{\ast}\}_n such that

lim⁡n→∞P(G(n,pn ; ([n]k))∈P)={0,if pn≪cn∗1,if pn≫cn∗.\lim_{n\to\infty} \mathbb{P}(\mathbb{G}(n,p_n\,; \,\binom{[n]}{k}) \in\mathcal{P}) = \begin{cases} 0,&\text{if } p_n \ll c_n^{\ast} \\ 1,&\text{if } p_n \gg c_n^{\ast}. \end{cases}

Bollobás–Thomason threshold conjecture. The property P\mathcal{P} has a threshold in G(n,p ; ([n]k))\mathbb{G}(n,p\,; \,\binom{[n]}{k}).

This conjecture proposes that the Bollobás–Thomason theorem for monotone increasing graph properties extends to these binomial random multigraphs, where each kk-set in ([n]k)\binom{[n]}{k} provides the underlying multigraph structure. The source gives no resolution evidence, so the conjecture is recorded as open.

References

Primary source

Christos Pelekis, “A binomial random multigraph”, arXiv:2401.00543 (2023).

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.