Weakly supercritical circumference conjecture for random planar graphs

Let P\mathcal P be the class of planar graphs, let P=P(n,m)RP(n,m)P=P(n,m)\in_R\mathcal P(n,m) be chosen uniformly at random, and let L1=L1(P)L_1=L_1(P) be the largest component of PP. Assume that

m=n/2+s,m=n/2+s,

where s=s(n)=o(n)s=s(n)=o(n) and s3n2s^3n^{-2}\to\infty. The circumference c(L1)c(L_1) is the length of the longest cycle in L1L_1.

Weakly supercritical circumference conjecture.

c(L1)=Θp(sn1/3).c(L_1)=\Theta_p\left(sn^{-1/3}\right).

This would sharpen the available lower and upper bounds for the circumference of the largest component in the weakly supercritical regime. The statement is presented as a consequence of the conjectured linear circumference of random cubic planar multigraphs.

Sources & referencesView supporting material

Primary source

Mihyun Kang and Michael Missethan, “Longest and shortest cycles in random planar graphs”, arXiv:2006.09697 (2021).

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.