|
|
|
A random graph is a Graph in which properties such as the number of Nodes, Edges, and connections between them are determined in some random way. Erdös and Rényi 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 Edges are almost certain to have it. This is known as a Phase Transition.
See also Graph (Graph Theory), Graph Theory
References
Bollobás, B. Random Graphs. London: Academic Press, 1985.
Steele, J. M. ``Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of
Random Trees.'' Prob. Eng. Inform. Sci. 1, 47-59, 1987.