Problem #746: Is it true that, almost surely, a random graph on $n$...

---

Progress

A conjecture of Erdős and Rényi [ErRe66], who proved that almost surely such a graph has a perfect matching (when $n$ is even).

This is true. Pósa [Po76] proved that almost surely a random graph with $\geq Cn\log n$ edges is Hamiltonian for some large constant $C$, and Korshunov [Ko77] proved that\[\geq \frac{1}{2}n\log n+\frac{1}{2}n\log\log n+w(n)n\]edges suffices, for any function $w$ which $\to \infty$ as $n\to \infty$.

Komlós and Szemerédi [KoSz83] proved the stronger result that with\[\frac{1}{2}n\log n+\frac{1}{2}n\log\log n+cn\]edges the probability that the graph is Hamiltonian tends to $e^{-e^{-2c}}$ as $n\to \infty$.