Logo
All Random Solved Random Open
SOLVED
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$.
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].