Random Graphs - Properties of Random Graphs

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 and what the probability is that is connected. In studying such questions, researchers often concentrate on the asymptotic behavior of random graphs—the values that various probabilities converge to as 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 . Next we remove randomly a fraction of nodes and leave only a fraction . There exists a critical percolation threshold below which the network becomes fragmented while above a giant connected component exists .

(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 often imply, via the Szemerédi regularity lemma, the existence of that property on almost all graphs.

In random regular graphs, G(n,r-reg) are the set of r-regular graphs with r=r(n) such that n and m are the natural numbers, 3≤r

The degree sequene of a graph depends only on the number of edges in the sets = {ij:1 ≤ j ≤ n, i≠j} ⊂, i=1, ..., n.

If edges, M in a random graph, is large enough to ensure that almost every has minimum degree at least 1, then almost every is connected and, if n is even, almost every has a perfect matching. In particular, the moment the last isolated vertex vanishes in almost every random graph, the graph becomes connected.

Almost every graph process on an even number of vertices with the edge raising the minimum degree to 1 or a random graph with slightly more than (n/4)log n edges and with probability close to 1 ensures that the graph has a complete matching, with exception of at most one vertex.

For some constant c, almost every labelled graph with n vertices and at least cn log n edges is Hamiltonian. With the probability tending to 1, the particular edge that increases the minimum degree to 2 makes the graph Hamiltonian.