Subcritical largest-component asymptotics near the hypercube scaling window

About 22 years old · traced to

Let pc(n)p_c(n) be the critical probability for the random subgraph of the nn-cube, let V=2nV=2^n, and write

p=pc(n)−ϵn−1.p=p_c(n)-\epsilon n^{-1}.

Assume ϵ→0\epsilon\rightarrow0 and ϵeδn→∞\epsilon e^{\delta n}\rightarrow\infty for every δ>0\delta>0. Let Cmax⁡{\mathcal C}_{\rm \max} be the largest component. Subcritical largest-component asymptotics conjecture. Almost surely,

∣Cmax⁡∣=2log⁡Vϵ2[1+o(1)].|{\mathcal C}_{\rm \max}|=\frac{2\log V}{\epsilon^2}[1+o(1)].

If instead ϵ→0\epsilon\rightarrow0 and ϵ2n/3→∞\epsilon 2^{n/3}\rightarrow\infty, then almost surely

∣Cmax⁡∣=Θ(2log⁡(ϵ3V)ϵ2).|{\mathcal C}_{\rm \max}|=\Theta\left(\frac{2\log(\epsilon^3V)}{\epsilon^2}\right).

These assertions extend the known subcritical estimates toward and beyond the scaling window, whose width is of order V−1/3V^{-1/3}.

References

Primary source

Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad, Gordon Slade and Joel Spencer, “Random subgraphs of finite graphs: III. The phase transition for the n-cube”, arXiv:math/0401071 (2004).

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.