Random graph

A random graph is obtained by starting with a set of n isolated vertices and adding successive edges between them at random. The aim of the study in this field is to determine at what stage a particular property of the graph is likely to arise. Different random graph models produce different probability distributions on graphs. Most commonly studied is the one proposed by Edgar Gilbert but often called the Erdős–Rényi model, denoted G(n,p). In it, every possible edge occurs independently with probability 0 p^m (1-p)^{N-m} with the notation N = \tbinom{n}{2}. A closely related model, also called the Erdős–Rényi model and denoted G(n,M), assigns equal probability to all graphs with exactly M edges. With 0 ≤ M ≤ N, G(n,M) has \tbinom{N}{M} elements and every element occurs with probability 1/\tbinom{N}{M}. Random regular graphs form a special case, with properties that may differ from random graphs in general. Once we have a model of random graphs, every function on graphs, becomes a random variable. The study of this model is to determine if, or at least estimate the probability that, a property may occur. ==Terminology==

The term 'almost every' in the context of random graphs refers to a sequence of spaces and probabilities, such that the error probabilities tend to zero. ==Properties==

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. In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs—the values that various probabilities converge to as n grows very large. Percolation theory characterizes the connectedness of random graphs, especially infinitely large ones. Percolation is related to the robustness of the graph (called also network). Given a random graph of n nodes and an average degree \langle k\rangle. Next we remove randomly a fraction 1-p of nodes and leave only a fraction p. There exists a critical percolation threshold p_c=\tfrac{1}{\langle k\rangle} below which the network becomes fragmented while above p_c a giant connected component exists. == Colouring ==

Given a random graph G of order n with the vertex V(G) = {1, ..., n}, by the greedy algorithm on the number of colors, the vertices can be colored with colors 1, 2, ... (vertex 1 is colored 1, vertex 2 is colored 1 if it is not adjacent to vertex 1, otherwise it is colored 2, etc.). == Random trees ==

A random tree is a tree or arborescence that is formed by a stochastic process. In a large range of random graphs of order n and size M(n) the distribution of the number of tree components of order k is asymptotically Poisson. Types of random trees include uniform spanning tree, random minimum spanning tree, random binary tree, treap, rapidly exploring random tree, Brownian tree, and random forest. == Conditional random graphs ==

Consider a given random graph model defined on the probability space (\Omega, \mathcal{F}, P) and let \mathcal{P}(G) : \Omega \rightarrow R^{m} be a real valued function which assigns to each graph in \Omega a vector of m properties. For a fixed \mathbf{p} \in R^{m}, conditional random graphs are models in which the probability measure P assigns zero probability to all graphs such that \mathcal{P}(G) \neq \mathbf{p} . Special cases are conditionally uniform random graphs, where P assigns equal probability to all the graphs having specified properties. They can be seen as a generalization of the Erdős–Rényi model G(n,M), when the conditioning information is not necessarily the number of edges M, but whatever other arbitrary graph property \mathcal{P}(G). In this case very few analytical results are available and simulation is required to obtain empirical distributions of average properties. ==History==

The earliest use of a random graph model was by Helen Hall Jennings and Jacob Moreno in 1938 where a "chance sociogram" (a directed Erdős-Rényi model) was considered in studying comparing the fraction of reciprocated links in their network data with the random model. Another use, under the name "random net", was by Ray Solomonoff and Anatol Rapoport in 1951, using a model of directed graphs with fixed out-degree and randomly chosen attachments to other vertices. The Erdős–Rényi model of random graphs was first defined by Paul Erdős and Alfréd Rényi in their 1959 paper "On Random Graphs" and independently by Gilbert in his paper "Random graphs". ==See also==