THE EVOLUTION OF RANDOM GRAPHS

THE EVOLUTION OF RANDOM GRAPHS

November 1984 | BÉLA BOLLOBÁS
The paper by Béla Bollobás examines the structure of random graphs $ G_M $, particularly focusing on the transition in their structure when the number of edges $ M $ is close to $ n/2 $. According to a result by Erdős and Rényi, when $ M \sim cn $ with $ c < 1/2 $, the largest component of a random graph has $ O(\log n) $ vertices, while for $ c > 1/2 $, a giant component of size $ (1 - \alpha_c + o(1))n $ emerges, where $ \alpha_c < 1 $. The paper provides detailed analysis of the structure of $ G_M $ when $ M $ is near $ n/2 $, showing that the giant component has approximately $ 4s $ vertices when $ M = n/2 + s $, with $ s = o(n) $ and $ s \geq (\log n)^{1/2}n^{2/3} $. It also gives precise estimates for the sizes of the rth largest components of $ G_M $ for fixed $ r $. The paper introduces the concept of graph processes and discusses the evolution of random graphs, highlighting the sudden changes in their structure. It proves that for $ t \geq n/2 + (\log n)^{1/2}n^{2/3} $, the graph $ G_t $ has a unique giant component with at least $ n^{2/3} $ vertices, while all other components have fewer than $ n^{2/3}/2 $ vertices. It also shows that graphs $ G_{n/2 - s} $ and $ G_{n/2 + s} $ have similar structures, with the giant component in $ G_{n/2 + s} $ having $ (4 + o(1))s $ vertices. The paper further explores the distribution of small components in random graphs, showing that for $ p = (1 + \varepsilon)/n $, the number of small components follows a Poisson distribution. It also provides results on the number of components of different sizes and their distributions, including the emergence of the giant component and the behavior of small components after time $ n/2 $. The paper concludes with theorems that describe the precise sizes of the largest components in random graphs and their distribution, as well as the behavior of small components in the context of graph processes. These results contribute to the understanding of the structure and evolution of random graphs, particularly around the critical point where the giant component emerges.The paper by Béla Bollobás examines the structure of random graphs $ G_M $, particularly focusing on the transition in their structure when the number of edges $ M $ is close to $ n/2 $. According to a result by Erdős and Rényi, when $ M \sim cn $ with $ c < 1/2 $, the largest component of a random graph has $ O(\log n) $ vertices, while for $ c > 1/2 $, a giant component of size $ (1 - \alpha_c + o(1))n $ emerges, where $ \alpha_c < 1 $. The paper provides detailed analysis of the structure of $ G_M $ when $ M $ is near $ n/2 $, showing that the giant component has approximately $ 4s $ vertices when $ M = n/2 + s $, with $ s = o(n) $ and $ s \geq (\log n)^{1/2}n^{2/3} $. It also gives precise estimates for the sizes of the rth largest components of $ G_M $ for fixed $ r $. The paper introduces the concept of graph processes and discusses the evolution of random graphs, highlighting the sudden changes in their structure. It proves that for $ t \geq n/2 + (\log n)^{1/2}n^{2/3} $, the graph $ G_t $ has a unique giant component with at least $ n^{2/3} $ vertices, while all other components have fewer than $ n^{2/3}/2 $ vertices. It also shows that graphs $ G_{n/2 - s} $ and $ G_{n/2 + s} $ have similar structures, with the giant component in $ G_{n/2 + s} $ having $ (4 + o(1))s $ vertices. The paper further explores the distribution of small components in random graphs, showing that for $ p = (1 + \varepsilon)/n $, the number of small components follows a Poisson distribution. It also provides results on the number of components of different sizes and their distributions, including the emergence of the giant component and the behavior of small components after time $ n/2 $. The paper concludes with theorems that describe the precise sizes of the largest components in random graphs and their distribution, as well as the behavior of small components in the context of graph processes. These results contribute to the understanding of the structure and evolution of random graphs, particularly around the critical point where the giant component emerges.
Reach us at info@study.space
[slides and audio] On the evolution of random graphs