Bollobás–Thomason threshold conjecture for binomial random multigraphs

From papers

Let k3k\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

limnP(G(n,pn;([n]k))P)={0,if pncn1,if pncn.\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.