random graph (infinite)


Suppose we have some method M of generating sequencesPlanetmathPlanetmath of letters from {p,q} so that at each generation the probability of obtaining p is x, a real number strictly between 0 and 1.

Let {ai:i<ω} be a set of vertices. For each i<ω , i1 we construct a graph Gi on the vertices a1,,ai recursively.

  • G1 is the unique graph on one vertex.

  • For i>1 we must describe for any j<ki when aj and ak are joined.

    • If k<i then join aj and ak in Gi iff aj and ak are joined in Gi-1

    • If k=i then generate a letter l(j,k) with M. Join aj to ak iff l(j,k)=p.

Now let Γ be the graph on {ai:i<ω} so that for any n,m<ω, an is joined to am in Γ iff it is in some Gi.

Then we call Γ a random graphMathworldPlanetmath. Consider the following property which we shall call f-saturation:

Given any finite disjoint U and V, subsets of {ai:i<ω} there is some an{ai:i<ω}(UV) so that an is joined to every point of U and no points in V.

Proposition 1

A random graph has f-saturation with probability 1.

Proof: Let b1,b2,,bn, be an enumeration of {ai:i<ω}(UV). We say that bi is correctly joined to (U,V) iff it is joined to all the members of U and non of the members of V. Then the probability that bi is not correctly joined is (1-x|U|(1-x)|V|) which is some real number y strictly between 0 and 1. The probability that none of the first m are correctly joined is ym and the probability that none of the bis are correctly joined is limnyn=0. Thus one of the bis is correctly joined.

Proposition 2

Any two countableMathworldPlanetmath graphs with f-saturation are isomorphicPlanetmathPlanetmath.

Proof: This is via a back and forth argument. The property of f-saturation is exactly what is needed.

Thus although the system of generation of a random graph looked as though it could deliver many potentially different graphs, this is not the case. Thus we talk about the random graph.

The random graph can also be constructed as a Fraisse limit of all finite graphs, and in many other ways. It is homogeneousPlanetmathPlanetmathPlanetmath and universalPlanetmathPlanetmathPlanetmath for the class of all countable graphs.

The theorem that almost every two infiniteMathworldPlanetmath random graphs are isomorphic was first proved in [1].

References

  • 1 Paul Erdős and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hung., 14:295–315, 1963.
Title random graph (infinite)
Canonical name RandomGraphinfinite
Date of creation 2013-03-22 13:32:18
Last modified on 2013-03-22 13:32:18
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 8
Author bbukh (348)
Entry type Definition
Classification msc 03C52
Classification msc 03C30
Classification msc 03C15
Classification msc 05C30
Related topic ExampleOfUniversalStructure
Related topic Homogeneous4
Defines random graph