Volume 266, Number 1, November 1984 | BÉLA BOLLOBÁS
The paper by Béla Bollobás examines the structure of random graphs \( G_M \) when the number of edges \( M \) is close to \( n/2 \). According to a fundamental result by Erdős and Rényi, the structure of \( G_M \) changes abruptly around \( M = cn \), where \( c = 1/2 \). For \( c < 1/2 \), the largest component has \( O(\log n) \) vertices, while for \( c > 1/2 \), \( G_M \) typically has a giant component with \( (1 - \alpha_c + o(1))n \) vertices, where \( \alpha_c < 1 \).
Bollobás aims to provide more precise results about the structure of \( G_M \) when \( M \) is close to \( n/2 \). He proves that if \( M = n/2 + s \), \( s = o(n) \), and \( s \geq (\log n)^{1/2}n^{2/3} \), then the giant component has \( (4 + o(1))s \) vertices. Additionally, he gives precise estimates for the order of the \( r \)-th largest component for any fixed \( r \).
The paper also discusses the distribution of small components in \( G_M \) and \( G_p \) (random graphs with edge probability \( p \)). For \( p = (1 + \varepsilon)/n \) with \( \varepsilon = o(1) \), the distribution of the number of small components tends to a Poisson distribution. For \( p < 1/n \), the distribution of small components is also analyzed, and for \( p > 1/n \), the distribution of small components is shown to be similar to that of \( G_{p'} \) with \( p' = (1 - \varepsilon)/n \).
Overall, the paper provides a detailed analysis of the structure of random graphs near the critical point \( M = n/2 \), highlighting the sudden emergence of a giant component and the behavior of smaller components.The paper by Béla Bollobás examines the structure of random graphs \( G_M \) when the number of edges \( M \) is close to \( n/2 \). According to a fundamental result by Erdős and Rényi, the structure of \( G_M \) changes abruptly around \( M = cn \), where \( c = 1/2 \). For \( c < 1/2 \), the largest component has \( O(\log n) \) vertices, while for \( c > 1/2 \), \( G_M \) typically has a giant component with \( (1 - \alpha_c + o(1))n \) vertices, where \( \alpha_c < 1 \).
Bollobás aims to provide more precise results about the structure of \( G_M \) when \( M \) is close to \( n/2 \). He proves that if \( M = n/2 + s \), \( s = o(n) \), and \( s \geq (\log n)^{1/2}n^{2/3} \), then the giant component has \( (4 + o(1))s \) vertices. Additionally, he gives precise estimates for the order of the \( r \)-th largest component for any fixed \( r \).
The paper also discusses the distribution of small components in \( G_M \) and \( G_p \) (random graphs with edge probability \( p \)). For \( p = (1 + \varepsilon)/n \) with \( \varepsilon = o(1) \), the distribution of the number of small components tends to a Poisson distribution. For \( p < 1/n \), the distribution of small components is also analyzed, and for \( p > 1/n \), the distribution of small components is shown to be similar to that of \( G_{p'} \) with \( p' = (1 - \varepsilon)/n \).
Overall, the paper provides a detailed analysis of the structure of random graphs near the critical point \( M = n/2 \), highlighting the sudden emergence of a giant component and the behavior of smaller components.