Lecture
In mathematics, a random graph is a general term for the probability distribution of graphs. Random graphs can be described simply by a probability distribution or by a random process creating these graphs. The theory of random graphs is located at the junction of graph theory and probability theory. From a mathematical point of view, random graphs are needed to answer the question about the properties of typical graphs. Random graphs have found practical application in all areas where complex networks need to be modeled - a large number of random graph models are known that reflect various types of complex networks in various areas. In a mathematical context, the term random graph almost always means the Erdёos – Rényi random graph model. In other contexts, any graph model means a random graph .
A random graph is obtained from a set of n isolated vertices by sequentially randomly adding edges connecting vertices. The purpose of modeling random graphs is to determine at what stage a certain property of the graph appears. Different models of random graphs give different probability distributions on a graph. The most commonly studied is the distribution proposed by Hilbert and denoted by G ( n , p ), in which any possible edge appears independently with probability 0 < p <1. The probability of a random graph with m edges is equal to pm (1 - p ) N - m . The Erdёos – Rényi model [en] close to it, denoted by G ( n , M ), gives the same probability to all graphs that have exactly M edges. If to designate 
with 0 ≤ M ≤ N , G ( n , p ) will contain {\ displaystyle 
elements and any element falls out with probability 
. This model can be considered as a snapshot for a certain point in time ( M ) of a random process on a graph. 
that starts with n vertices with no edges, and at each step a new edge is added, chosen uniformly from the set of missing edges.
If we start from an infinite set of vertices and choose each possible edge independently with probability 0 < p <1, we get an object G , called an infinite random graph . Except for the trivial cases, when p is 0 or 1, this G almost certainly has the following properties:
If any n + m elements are given
, there is a vertex c in V that is adjacent to each vertex
and not connected to any of
.
It turns out that if the set of vertices is countable, then there exists, up to [en] of the isomorphism, a unique graph with such properties, namely, the Rado graph. Thus, any countable infinite graph is almost certainly a Rado graph, which for this reason is sometimes called simply a random graph . However, the analogous result is not valid for uncountable graphs for which there are many (non-isomorphic) graphs satisfying the above condition.
Another model that generalizes the Hilbert model of a random graph is the model of a random scalar product . A graph of a random dot product connects a real vector with each vertex. The probability of the edge uv between any vertices u and v is some function of the scalar product u • v of the corresponding vectors.
Network probability matrices model random graphs through edge probabilities 
so that this edge 
exists in the specified time period. This model can be extended to oriented and non-oriented graphs, weighted and not weighted, to static and dynamic.
For M ≃ pN , where N is the maximum possible number of edges, the models G ( n , M ) and G ( n , p ) are most often used, almost always interchangeable.
A random regular graph forms a special case with properties that may differ from random graphs in the general case.
If we have a random graph model, any function on the graphs becomes a random variable. The task of studying this model is to determine, or at least estimate the probability of a property appearing.
The term “almost reliably” in the context of random graphs refers to a sequence of spaces and probabilities, such that the probability of error tends to zero.
The theory of random graphs studies typical properties of random graphs that are performed with a high degree of probability for graphs obtained for a certain distribution. For example, we can ask for given values of n and p , what is the probability that G ( n , p ) is connected. When studying such questions, researchers often concentrate on the asymptotic behavior of random graphs — values that different probabilities tend to as n grows. The percolation theory describes the connectedness of random graphs, especially unlimitedly large ones.
Percolation is related to the stability of a graph (also called a network). Let a random graph with n vertices and average degree be given 
. Remove the random 1− p part of the edges and leave the p part. There is a critical threshold for percussion 
, below which the network becomes fragmented, while above pc there are huge connectivity components.
Random graphs are widely used in the probabilistic method when trying to prove the existence of graphs with certain properties. The existence of a property on random graphs can often be a consequence, according to the Lemma of regularity of Szemerédi, the existence of this property for almost all graphs.
For random regular graphs, [en] G ( n , r -reg) is the set of r- regular graphs with r = r ( n ), such that n and m are positive integers, 3 ≤ r < n , and rn = 2 m evenly
The sequence of degrees of a graph G in Gn depends only on the number of edges in the sets
If the set of edges M in a random graph GM is large enough that almost all GM have a minimum degree of at least 1, then almost any GM is connected and, for even n , almost any GM contains a perfect matching. In particular, at the moment when the last isolated vertex disappears, in almost all random graphs, the graph becomes connected
Almost any process of constructing a graph with an even number of vertices when it reaches the minimum degree of 1 or a random graph when it reaches slightly more than ( n / 4) log ( n ) edges with a probability close to 1 ensures the existence of a complete match, except perhaps one vertex.
For some constant c, almost every labeled graph with n vertices and at least cn log ( n ) edges is Hamiltonian. With probability tending to 1, the addition of an edge, increasing the minimum degree of the graph to 2, makes it Hamiltonian.
If a random graph G of order n with vertices V ( G ) = {1, ..., n } is given, the coloring can be obtained using the greedy algorithm (vertex 1 is colored with color 1, vertex 2 gets color 1 if it is not adjacent 1, otherwise it gets color 2, and so on).
A random tree is a tree or oriented tree formed by a random process. In a large range of random graphs of order n and size M ( n ), the distribution of the number of trees of order k is asymptotically subject to the Poisson law. Types of random trees include uniform tightening trees [en], random minimal tightening trees, random binary trees [en], Cartesian trees, quickly viewed random trees, en Brownian trees, and random forests.
Random graphs were first defined by Erdös and Rényi in the 1959 book On Random Graphs and independently by Gilbert in his article Random Graphs.
Comments
To leave a comment
Probability theory. Mathematical Statistics and Stochastic Analysis
Terms: Probability theory. Mathematical Statistics and Stochastic Analysis