|
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.
Random graph models A random graph is obtained by starting with a set of n vertices and adding edges between them at random. Different random graph models produce different probability distributions on graphs. The most commonly studied model, called G(n,p), includes each possible edge independently with probability p. A closely related model, G(n,M) assigns equal probability to all graphs with exactly M edges. Both models can be viewed as snapshots at a particular time of the random graph process , which is a stochastic process that starts with n vertices and no edges and at each step adds one new edge chosen uniformly from the set of missing edges. Consider a graph with vertices contained in a set , as a binary relation by defining as: if there is an edge between and . Conversely each symmetric relation on gives rise to a graph on . We can also construct an object called an infinite random graph. A random graph is a graph on an infinite set satisfying the following properties: i) is irreflexive ii) is symmetric iii) Given any elements there is such that is related to and is not related to . It turns out that if the set is countable there is a unique random graph up to isomorphism (that is any two countable random graphs are isomorphic). This is an example of an -categorical theory. Properties of random graphs The theory of random graphs studies typical properties of random graphs, those that hold with high probability for graphs drawn from a particular distribution. For example, we might ask for a given value of n and p what the probability is that G(n,p) is connected, meaning that it has a path between any two vertices. In studying such questions, random graph theorists often concentrate on the limit behavior of random graphs—the values that various probabilities converge to as n grows very large. (threshold functions, evolution of G~) Random graphs are widely used in the probabilistic method, where one tries to prove the existence of graphs with certain properties. The existence of a property on a random graph can be translated to the existence of the property on almost all graphs using the famous Szemerédi regularity lemma. History Random graphs were first defined by Paul Erdős and Alfréd Rényi in their 1959 paper "On Random Graphs I" published in Publ. Math. Debrecen 6, p. 290–297. See also | ||||||||
|
| |||||||||
 |
|
| |