Skip to content

Erdős Problem #745

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

The maintained source literally asks about the second-largest component of G(n,p) with p=1/n and claims it has O(log n) vertices almost surely. This is MATHEMATICALLY INCOMPATIBLE with the critical random-graph theory: at p=1/n, the largest components (including the second) have size scale n^(2/3), not logarithmic. The cited 1980 Komlós–Sulyok–Szemerédi theorem concerns the SUPERCRITICAL p=λ/n with fixed λ>1 and is not a proof of the critical statement. Source must be corrected before admission.

A small example

At p=1/n the expected degree is approximately one, the critical phase-transition location. In Aldous's 1997 critical scaling, the joint ranked component sizes multiplied by n^(−2/3) converge to nondegenerate random excursion lengths, including a positive second excursion in the limit. By contrast, for fixed λ>1, a linear-size giant component emerges while all components outside it are O(log n) w.h.p. These are different parameter regimes, not two estimates for the same graph.

What is known

The authors' published KSS80 text, Second largest component in a random graph, Studia Sci. Math. Hungar. 15 (1980), 391–395, explicitly assumes p=λ/n with λ>1 and states that the second-largest component has logarithmic size. David Aldous, 'Brownian excursions, critical random graphs and the multiplicative coalescent', Ann. Probability 25 (1997), 812–854, establishes joint n^(2/3) critical component scaling; the author research page confirms all leading components have that order. Thus the maintained #745 text's p=1/n and its O(log n) proved attribution cannot simultaneously hold. This is a source-parameter error, NOT a novel disproof of random graph theory.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: KSS80's logarithmic second component assumes supercritical p=lambda/n lambda>1; at critical p=1/n scaling is n^(2/3), contradicting the maintained attribution.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

ERDOS-745-CRITICAL_VS_SUPERCRITICAL_SOURCE_REPAIR. Obtain original Er81 problem wording and primary KSS80 and Aldous pages, establish whether the intended original edge probability was λ/n for λ>1, then correct only after source lock. Preserve critical p=1/n result at n^(2/3) with exact probability/limit quantifiers; no public admission until resolved.

Sources and claim boundaries

Maintained Erdős #745; KSS80 published authors' text; Aldous 1997 critical random graphs; original issue-bound GCL audit. Primary full proof pages not all inspected; protected source publication and live browser validation have occurred; V2 admission remains HELD for historical probability-parameter reconstruction.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2016 — 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