Local resilience conjecture for Hamiltonicity in random geometric graphs

From papers

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 d1d\geq1, there exists a constant C=C(d,ϵ)>0C=C(d,\epsilon)>0 such that, for rC(logn/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.

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

No solutions have been posted yet.