Hamiltonicity conjecture for randomly perturbed graphs with geometric randomness

From papers

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,

HGd(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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.