Problem 745

Describe the size of the second largest component of the random graph on $n$ vertices, where each edge is included independently with probability $1/n$ .

Source: erdosproblems.com/745

Graph theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

PROVED is the site's label, which credits Komlós, Sulyok and Szemerédi's 1980 paper [KSS80] (Studia Sci. Math. Hungar. 15 (1980), 391--395) with proving Erdős's expectation that the second largest component has size $\ll\log n$ almost surely. The standing in the frontmatter is derived from the claim pages and differs from the label. [KSS80] is not held (the routes tried are recorded below), and its theorem is known second-hand, from the site's commentary, from a thread comment of 25 August 2026, which says that [KSS80] assumes $\lambda>1$ strictly, and from the docstring of an external Lean file describing "the KSS logarithmic upper bound" as holding "for each fixed supercritical parameter": for every fixed $\lambda>1$ the second largest component of $G(n,\lambda/n)$ has $O(\log n)$ vertices with high probability. Erdős himself attests the resolution in the added-in-proof sentence of his 1981 paper ("These questions were cleared up by Komlós and Szemerédi", [Er81], Part VIII, copy p. 16). The problem fixes $p=1/n$ , that is $\lambda=1$ , where the theorem says nothing and where the second largest component is not of order $\log n$ but of order $n^{2/3}$ , the order of the largest components in the critical window (Erdős and Rényi 1960 [ErRe60] prove that order at $N\sim n/2$ for the greatest tree, Theorem 7c, and state it for the largest component in their summary on p. 52; Aldous 1997 [Al97] proves the limit law of all the largest components, the second included, at $p=1/n$ ). So Erdős's expectation, stated for the whole process ("never be large, perhaps not much larger than $\log n$ and certainly $o(n^\varepsilon)$ ", [Er81], copy p. 16), holds for fixed $\lambda>1$ and fails at the asked parameter. The theorem is correct, but it answers the supercritical case the site's label credits ( $\lambda>1$ ), not the Statement ( $p=1/n$ ), so it does not count toward the problem's standing, and its claim page, Komlós, Sulyok and Szemerédi 1980, is rejected. The accepted full claim is Aldous 1997, refereed: for fixed $t$ the component sizes of $G(n,1/n+tn^{-4/3})$ , scaled by $n^{-2/3}$ , converge in law to Brownian excursion lengths, so at $t=0$ , the asked parameter, $L_2=\Theta_{\mathbb P}(n^{2/3})$ ; this describes what the problem asks for, so the claim's value is solved. Two Lean developments reach the same order and are pending full claims: Boris Alexeev's Alexeev 2026, which also gives the logarithmic order with its coefficient for every fixed $\lambda\ne1$ , and Jingxuan Ding's Ding 2026, a five-regime atlas of the sparse evolution of the uniform model $G(n,M)$ . This corpus has built neither, and the search recorded below found the site's label unchanged. Whether the label can stand at the literal parameter is a question of the catalog's labeling that this page records; the two parameters are stated side by side below.

KSS80: Komlós, J. and Sulyok, M. and Szemerédi, E., Second largest component in a random graph. Studia Sci. Math. Hungar. 15 (1980), 391--395 (zbMATH record 3821793, accessed 2026-09-19: MSC 05C80, 05C40, 60C05; no review text served; no DOI, no Crossref or OpenAlex record). Not held: the journal has no open archive (routes tried under Search scope). Its theorem is second-hand as stated above.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25--42, doi:10.1007/BF02579174 (Crossref record); Part VIII, "Two Problems on Random Graphs and Hypergraphs", p. 16 of the retyped copy, which has its own pagination. Library home: Erdős 1981.
ErRe60: Erdős, P. and Rényi, A., On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17--61 (received 28 December 1959). The paper that found the singularity Erdős describes, for the uniform random graph $\Gamma_{n,N}$ with $N\sim cn$ edges. Library home: Erdős and Rényi 1960 (the Rényi archive's scan, its item 1960-10; the card carries the row for this problem). Its component-size results at $N\sim n/2$ , on printed pp. 47--49, 52--53 and 56--57 (pp. 31--33, 36--37 and 40--41 of the archive's PDF): Theorem 7a (pp. 47--48), for $N\sim cn$ with $c\ne\tfrac12$ the greatest tree component has $\tfrac1\alpha(\log n-\tfrac52\log\log n)\pm\omega_n$ points with probability tending to $1$ , $\alpha=2c-1-\log2c$ , and for $c<\tfrac12$ this tree is the largest component (remark, pp. 48--49); Theorem 7c (p. 49), "If $N\sim\tfrac n2$ and $\Delta_{n,N}$ denotes again the number of points of the greatest tree contained in $\Gamma_{n,N}$ , we have for any sequence $\omega_n$ tending to $+\infty$ for $n\to+\infty$ (7.11) $\lim\mathbf P(\Delta_{n,N}\ge n^{2/3}\omega_n)=0$ and (7.12) $\lim\mathbf P(\Delta_{n,N}\ge n^{2/3}/\omega_n)=1$ "; the summary of § 9 (p. 52), "the largest component of $\Gamma_{n,N(n)}$ is of order $\log n$ for $\frac{N(n)}n\sim c<\tfrac12$ , of order $n^{2/3}$ for $\frac{N(n)}n\sim\tfrac12$ and of order $n$ for $\frac{N(n)}n\sim c>\tfrac12$ . This double 'jump' of the size of the largest component when $\frac{N(n)}n$ passes the value $\tfrac12$ is one of the most striking facts concerning random graphs", whose $n^{2/3}$ clause for the largest component is stated in the summary and is the statement of no numbered theorem of the paper (the § 9 theorems assume $c>\tfrac12$ ); and Theorem 9b (p. 56), for $N(n)\sim cn$ with $c>\tfrac12$ the greatest component has $(G(c)+o(1))n$ points with probability tending to $1$ , $G(c)=1-x(c)/(2c)$ with $x(c)e^{-x(c)}=2ce^{-2c}$ , $0<x(c)<1$ . The paper has no statement about the second largest component anywhere in its 45 pages, and its " $N\sim\tfrac n2$ " is asymptotic equivalence, not the window $\tfrac n2+O(n^{2/3})$ of the later critical theory. The proofs are not checked by this corpus.
Al97: Aldous, D., Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), no. 2, 812--854, doi:10.1214/aop/1024404421 (zbMATH Zbl 0877.60010). Not held. Its Corollary 2 is paged on the claim page Aldous 1997.

Problem 745

Status

Proof claims

Discussion