Asymptotic local resilience of binomial random graphs for Hamiltonicity

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 pKlnnnp \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.

Sources & referencesView supporting material

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.