Erdős Problem #746
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
For fixed ε>0, consider the uniformly random graph on n vertices with at least (1/2+ε)n log n edges. Erdős–Rényi asked whether it has a Hamiltonian cycle with probability tending to one. It does: the maintained catalogue says PROVED. The probability model is G(n,m), edges chosen uniformly with a specified total, not an arbitrary deterministic graph with that many edges.
A small example
The cycle C_5 is a five-vertex graph with exactly five edges and a Hamiltonian cycle. K_5 also has a Hamiltonian cycle, but examples do not establish a high-probability theorem for random graphs; graphs with a large number of edges can be disconnected when edge placement is adversarial.
What is known
Pósa 1976 gave an upper with sufficiently large C n log n edges. Korshunov 1977 established a near-threshold upper m≥(n/2)log n+(n/2)loglog n+ω(n)n. Komlós–Szemerédi 1983 proved a sharper window law: if m=(n/2)log n+(n/2)loglog n+c n, the Hamiltonicity probability tends to exp(−exp(−2c)). The maintained source's 2025 correction credits Korshunov, not Komlós–Szemerédi, for the ω(n) margin theorem. These are source-proven classical results, not a new GCL derivation. The integer rounding of m and finite-n disconnectedness must not be conflated with asymptotic probability.
GCL's current state
The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.
Critical source-scope distinction: Korshunov provenance of n loglog n, Komlós–Szemerédi refined random G(n,m) window, not deterministic.
What remains
ERDOS-746-HAMILTONIC_THRESHOLD_PROVENANCE. Source-check Korshunov 1977 and Komlós–Szemerédi 1983 original statements, translate G(n,p) vs G(n,m) threshold, and verify finite graph cycle/distinctness fixtures. State exact ε fixed and limit n→∞; no deterministic edge-density implication.
Sources and claim boundaries
Maintained Erdős #746; original issue-bound GCL audit. Primary full proof pages not all inspected; no protected publication, real browser mathematics validation or V2 admission.
Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2017 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.