Hamiltonicity conjecture for randomly perturbed graphs with geometric randomness

About 5 years old · traced to

Let dgeq1dgeq1 be an integer, let α=α(n)∈(0,1/2)\alpha=\alpha(n)\in(0,1/2), and let HH be an nn-vertex graph with minimum degree at least αn\alpha n. Write Gd(n,r)G^d(n,r) for the random geometric graph generated by nn independent uniform points in [0,1]d[0,1]^d, with edges between points at distance at most rr. Hamiltonicity conjecture. For some constant CC, asymptotically almost surely,

H∪Gd(n,(−Clog⁡α/n)1/d)H\cup G^d(n,(-C\log\alpha/n)^{1/d})

is Hamiltonian. This would extend the known threshold for binomial random perturbations to random geometric graphs and would be best possible up to the value of CC; the conjecture concerns the regime in which α=α(n)\alpha=\alpha(n) tends to 00.

References

Primary source

Alberto Espuny Díaz, “Hamiltonicity of graphs perturbed by a random geometric graph”, arXiv:2102.02321 (2022).

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.