A phase transition is a change in macroscopic behavior as a parameter crosses a critical threshold. Erdős and Rényi (1960) showed that for
many monotone-increasing properties of random graphs,
graphs of a size slightly less than a certain threshold
are very unlikely to have the property, whereas graphs
with a few more graph edges are almost certain to have
it. This is known as a phase transition (Janson et al. 2000, p. 103).
Erdős, P. and Rényi, A. "On the Evolution of Random Graphs." Publ. Math. Inst. Hungar. Acad. Sci.5, 17-61,
1960.Janson, S.; Łuczak, T.; and Ruciński, A. "The Phase
Transition." Ch. 5 in Random
Graphs. New York: Wiley, pp. 103-138, 2000.
