Linear circumference conjecture for random cubic planar multigraphs

Let K=K(2n,3n)K=K(2n,3n) be a graph chosen uniformly at random from the class of all cubic planar multigraphs on vertex set [2n][2n]. Its circumference c(K)c(K) is the length of its longest cycle.

Linear circumference conjecture.

c(K)=Θp(n).c(K)=\Theta_p(n).

Random cubic planar multigraphs cannot have Hamiltonian cycles because linearly many vertices have an attached loop, but the conjecture asserts that they nevertheless have cycles of linear length with high probability. This would determine the asymptotic order of the circumference and is used to obtain the corresponding weakly supercritical result for random planar graphs.

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.