Local resilience conjecture for Hamiltonicity in random geometric graphs
Local resilience conjecture for Hamiltonicity in random geometric graphs
Let be the -dimensional random geometric graph on random points, with edges joining pairs at distance at most . A graph is an -subgraph of if it is obtained by retaining, at every vertex, at least a -fraction of its incident edges.
Local resilience conjecture. For every and integer , there exists a constant such that, for , asymptotically almost surely every -subgraph of 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.
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, Lyuben Lichev and Alexandra Wesolek, “On the local resilience of random geometric graphs with respect to connectivity and long cycles”, arXiv:2406.09921 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.