.

The
theory of random graphs lies at the intersection between graph theory
and probability theory, and studies the properties of typical random
graphs.

vertices and adding edges between them at random.

NotationG(n,p) : in which every possible edge occurs independently with probability *p* (the Edgar Gilbert model). Thus, the expected number of edges is *pn*(*n* − 1)/2.

**Percolation Theory**

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 <k>. Next we remove randomly a fraction 1-p of nodes and leave only a fraction p. There exists a critical percolation threshold pc = 1/<k> below which the network becomes fragmented while above pc a giant connected component exists.

OR

Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom?

**Bond Percolation: **Assume that some liquid is poured on top of some porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is modelled mathematically as a three-dimensional network of n × n × n points (or vertices/sites) the connections (or edges/bonds) between each two neighbors may be open (allowing the liquid through) with probability p, or closed with probability 1 – p, and they are assumed to be independent. Therefore, for a given p, what is the probability that an open path exists from the top to the bottom?

**Site Percolation**:

When a site is occupied with probability *p* or empty (its edges are also removed) with probability *1-p*, the problem is called "site percolation".

Detail of a bond percolation on the square lattice in two dimensions with percolation probability *p* = 0.51

As is quite typical, it is actually easier to examine infinite
networks than just large ones. In this case the corresponding question
is: does an infinite open cluster exist? That is, is there a path of
connected points of infinite length "through" the network? By

Kolmogorov's zero-one law, for any given

*p*, the probability that an infinite cluster exists is either zero or one.

Since this probability is an increasing function of *p* (proof via coupling argument), there must be a **critical** *p* (denoted by *p*_{c})
below which the probability is always 0 and above which the probability
is always 1. In practice, this criticality is very easy to observe.
Even for *n* as small as 100, the probability of an open path from
the top to the bottom increases sharply from very close to zero to very
close to one in a short span of values of *p*.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 famous

Szemerédi regularity lemma, the existence of that property on almost all graphs.

## Random Tree