How Erdős and Rényi Pioneered the Study of Random Graphs
In the late 1950s, Hungarian mathematicians Paul Erdős and Alfréd Rényi revolutionized mathematics by merging graph theory with probability theory. This article provides an overview of how the duo initiated the systematic study of random graphs through a series of eight landmark papers starting in 1959. By introducing the Erdős–Rényi model, they shifted the focus of graph theory from analyzing static, deterministic structures to observing how networks evolve dynamically as connections are added at random. Their discoveries regarding threshold phenomena and the sudden emergence of the "giant component" laid the foundational mathematics for modern network science, computer science, and statistical physics.
The Shift from Deterministic to Probabilistic
Prior to 1959, graph theory was primarily a deterministic field. Mathematicians studied specific graphs with fixed vertices (nodes) and edges (connections) to determine their exact properties.
Paul Erdős had previously used the "probabilistic method" in 1947 to prove the existence of graphs with certain properties without actually constructing them. He did this by showing that the probability of a randomly generated graph having a specific property was greater than zero. However, it was his collaboration with probability theorist Alfréd Rényi that transformed this clever proof technique into an entirely new branch of mathematics: the theory of random graphs.
The 1959 Breakthrough: The Erdős–Rényi Model
Erdős and Rényi officially launched the field with their 1959 paper, On Random Graphs I. In this work, they introduced a precise mathematical definition for generating a random graph, now universally known as the Erdős–Rényi model, denoted as \(G(n, M)\).
Their model operates on a straightforward principle:
- Start with a fixed number of isolated vertices, \(n\).
- Choose a specific number of edges, \(M\), to add between these vertices.
- Select one graph uniformly at random from the collection of all possible graphs that have exactly \(n\) vertices and \(M\) edges.
Equivalently, they viewed this as a dynamic process. They imagined starting with \(n\) disconnected vertices and adding \(M\) edges one by one, choosing each new edge randomly from the remaining unlinked pairs of vertices.
The Evolution of Random Graphs and Phase Transitions
In 1960, the duo published their most influential paper on the subject, On the Evolution of Random Graphs. Instead of just looking at a static random graph, they asked what happens to the structure of a graph as \(M\) (the number of edges) increases over time.
They discovered that random graphs do not grow gradually; instead, they undergo sudden, dramatic changes known as "phase transitions," much like water suddenly freezing into ice at a specific temperature.
Erdős and Rényi proved that many graph properties have a sharp threshold. If the number of edges is slightly below the threshold, almost no random graphs will have the property. If the number of edges is slightly above the threshold, almost all of them will.
The Emergence of the Giant Component
The most famous phase transition discovered by Erdős and Rényi is the emergence of the "giant component." They tracked the size of the largest connected cluster of vertices as edges were randomly added to \(n\) vertices:
- Subcritical Phase: When the number of edges is less than \(n/2\) (meaning the average degree of each vertex is less than 1), the graph consists only of tiny, isolated trees and components.
- Critical Point: When the number of edges reaches approximately \(n/2\) (an average degree of 1), a phase transition occurs. The small components suddenly merge.
- Supercritical Phase: Just past this threshold, a single "giant component" rapidly forms, containing a significant fraction of all the vertices in the graph.
- Connectivity: As even more edges are added, reaching a threshold proportional to \(\frac{1}{2} n \ln(n)\), the isolated vertices are finally absorbed, and the entire graph becomes fully connected.
Answering Fundamental Questions with Probability
By treating graph edges as random variables, Erdős and Rényi used the tools of probability theory—such as expected value, variance, and the law of large numbers—to answer structural questions. They didn't seek to prove that every graph with a certain number of edges had a specific property. Instead, they proved that a property holds "almost surely," meaning the probability approaches 100% as the number of vertices grows toward infinity.
Through their collaborative insight, Erdős and Rényi demonstrated that randomness actually produces highly predictable outcomes on a large scale, single-handedly initiating the field of probabilistic combinatorics.