---

Claim. Theorem 3 of L. Pósa, Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), no. 4, 359--364 (received 26 October 1974), p. 364, paged at Theorem 3: "Let us consider $n$ vertices and place $[c_1n\log n]$ edges between them at random. The graph $G$ so arising contains a Hamiltonian circuit with probability tending to 1. ($c_1$ is a number for which Theorem 2 holds.)" Theorem 2 (p. 363) is the same statement in the binomial model with edge probability $(c_1\log n)/n$, for a sufficiently large $c_1$. The graph of Theorem 3 is chosen uniformly among the graphs with exactly $[c_1n\log n]$ edges on $n$ labeled vertices, the model of Problem 746. Hamiltonicity is preserved by adding edges, so for every fixed $\epsilon\ge c_1-\tfrac12$ the random graph with at least $(\tfrac12+\epsilon)n\log n$ edges is almost surely Hamiltonian. The issue carries the year only, so this page's name uses the first day of it.

Covers. Every fixed $\epsilon\ge c_1-\tfrac12$, where $c_1$ is a constant for which Pósa's Theorem 2 holds (the paper names none; Komlós and Szemerédi's abstract reports that $c>3$ suffices); smaller $\epsilon$ are not covered. The full statement is proved on the claim pages Korshunov and Komlós and Szemerédi.

Depends on. Nothing in this wiki.

Acceptance. Refereed: Discrete Mathematics 14 (1976), no. 4. The site's curator, Thomas Bloom, credits the theorem in the problem's commentary, and Erdős's 1982 Singapore paper (§ 1, p. 69) says the conjecture "was proved by Pósa in a very ingenious way with $cn\log n$ instead of $(\tfrac12+\varepsilon)n\log n$". Both are context, not evidence: the label PROVED rests on Korshunov and on Komlós and Szemerédi, and the problem lists no parts.