Hamiltonicity threshold conjecture via linear forests

Let nn be even, let α(0,1/2)\alpha\in(0,1/2) be fixed, and set d=αnd=\alpha n. Let HnH_n be the complete bipartite graph with parts of sizes dd and ndn-d.

Hamiltonicity threshold conjecture. The sharp dd-threshold for HnG(n,p)H_n\cup G(n,p) to be Hamiltonian coincides with the sharp threshold for G(nd,p)G(n-d,p) to contain a linear forest with n2dn-2d edges.

A linear forest in the random graph on the larger part can be incorporated into a Hamilton cycle of the perturbed complete bipartite graph. The paper does not give an explicit threshold because the size of the largest linear forest in a sparse random graph has not been determined in the literature.

Sources & referencesView supporting material

Primary source

Alberto Espuny Díaz and Richarlotte Valérà Razafindravola, “How many random edges make an almost-Dirac graph Hamiltonian?”, arXiv:2410.14447 (2024).

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.