Asymptotic local resilience of binomial random graphs for Hamiltonicity
Asymptotic local resilience of binomial random graphs for Hamiltonicity
Let be the binomial random graph on vertices, let denote the property of being Hamiltonian, and let denote the local resilience of with respect to Hamiltonicity. Binomial Hamiltonicity resilience conjecture. For every there exists an integer such that for every , w.h.p.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.