Hamiltonicity threshold conjecture via linear forests
Hamiltonicity threshold conjecture via linear forests
Let be even, let be fixed, and set . Let be the complete bipartite graph with parts of sizes and .
Hamiltonicity threshold conjecture. The sharp -threshold for to be Hamiltonian coincides with the sharp threshold for to contain a linear forest with 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.