Abstract
Although the theory of random graphs is one of the youngest branches of graph theory, in importance it is second to none. It began with some sporadic papers of Erdős in the 1940s and 1950s, in which Erdős used random methods to show the existence of graphs with seemingly contradictory properties. Among other results, Erdős gave an exponential lower bound for the Ramsey number R(s, s); i.e., he showed that there exist graphs of large order such that neither the graph nor its complement contains a K s.He also showed that for all natural numbers k and g there are k-chromatic graphs of girth at least g. As we saw in Chapters V and VI, the constructions that seem to be demanded by these assertions are not easy to come by. The great discovery of Erdős was that we can use probabilistic methods to demonstrate the existence of the desired graphs without actually constructing them. This phenomenon is not confined to graph theory and combinatorics: probabilistic methods have been used with great success in the geometry of Banach spaces, in Fourier analysis, in number theory, in computer science—especially in the theory of algorithms—and in many other areas. However, there is no area where probabilistic methods are more natural and lead to more striking results than in combinatorics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer Science+Business Media New York
About this chapter
Cite this chapter
Bollobás, B. (1998). Random Graphs. In: Modern Graph Theory. Graduate Texts in Mathematics, vol 184. Springer, New York, NY. https://doi.org/10.1007/978-1-4612-0619-4_7
Download citation
DOI: https://doi.org/10.1007/978-1-4612-0619-4_7
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-98488-9
Online ISBN: 978-1-4612-0619-4
eBook Packages: Springer Book Archive