Local resilience conjecture for Hamiltonicity in random geometric graphs

About 2 years old · traced to

Let Gd(n,r)G_d(n,r) be the dd-dimensional random geometric graph on nn random points, with edges joining pairs at distance at most rr. A graph is an (1/2+ϵ)(1/2+\epsilon)-subgraph of Gd(n,r)G_d(n,r) if it is obtained by retaining, at every vertex, at least a (1/2+b5)(1/2+b5)-fraction of its incident edges.

Local resilience conjecture. For every ϵ∈(0,1/2]\epsilon\in (0,1/2] and integer d≥1d\geq1, there exists a constant C=C(d,ϵ)>0C=C(d,\epsilon)>0 such that, for r≥C(log⁡n/n)1/dr\geq C(\log n/n)^{1/d}, asymptotically almost surely every (1/2+ϵ)(1/2+\epsilon)-subgraph of Gd(n,r)G_d(n,r) is Hamiltonian.

This would extend the corresponding local resilience results for binomial random graphs and random regular graphs to random geometric graphs. The conjecture is posed as an analogue of known sharp Hamiltonicity results, and its status is open.

References

Primary source

Alberto Espuny Díaz, Lyuben Lichev and Alexandra Wesolek, “On the local resilience of random geometric graphs with respect to connectivity and long cycles”, arXiv:2406.09921 (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.