Problem Statement
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$.
Categories:
Graph Theory
Progress
Erdős believed that almost surely the second largest component has size $\ll \log n$. This is true, as proved by Komlós, Sulyok, and Szemerédi [KSS80].Source: erdosproblems.com/745 | Last verified: January 16, 2026