Subcritical largest-component asymptotics near the hypercube scaling window

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)ϵn1.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=2logVϵ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 V1/3V^{-1/3}.

Sources & referencesView supporting material

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.