Skip to content

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.

Back to catalogue · Compendium introduction