Claims

../

1976_01_01_posa: Pósa (Discrete Math. 14 (1976)) proves that a random graph with [c_1 n log n] edges is almost surely Hamiltonian for a large constant c_1, which settles Problem 746 for every fixed ε ≥ c_1 - 1/2; refereed.

1976_01_22_korshunov: Korshunov proves that almost every graph with n labeled vertices and k edges is Hamiltonian exactly when k = (n/2)(log n + log log n + φ(n)), φ(n) → ∞, answering Problem 746; announced 1976, a part proved 1977, in full in 1985.

1983_01_01_komlos_szemeredi: Komlós and Szemerédi prove that with (n/2) log n + (n/2) log log n + c n edges the probability of a Hamiltonian cycle tends to exp(-exp(-2c)), and to 1 as c → ∞, answering Problem 746; refereed in Discrete Mathematics 43 (1983).

---