Asymptotic local resilience of binomial random graphs for Hamiltonicity

At least 16 years old · documented by

Let G(n,p)\mathcal{G}(n,p) be the binomial random graph on nn vertices, let HAM\mathcal{HAM} denote the property of being Hamiltonian, and let rℓ(G,HAM)r_\ell(G,\mathcal{HAM}) denote the local resilience of GG with respect to Hamiltonicity. Binomial Hamiltonicity resilience conjecture. For every ε>0\varepsilon>0 there exists an integer K(ε)>0K(\varepsilon)>0 such that for every p≥Kln⁡nnp \geq \frac{K\ln n}{n}, w.h.p.

∣rℓ(G(n,p),HAM)−np2∣≤εnp.\left|r_\ell(\mathcal{G}(n,p),\mathcal{HAM})-\frac{np}{2}\right|\leq\varepsilon np.

This predicts that throughout the logarithmic-degree range and above, the local resilience of a typical binomial random graph is asymptotic to half its expected degree. The paper notes that the corresponding conjectural order was previously suggested by Sudakov and Vu.

References

Primary source

Sonny Ben-Shimon, Michael Krivelevich and Benny Sudakov, “Local resilience and Hamiltonicity Maker-Breaker games in random-regular graphs”, arXiv:0911.4351 (2010).

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.