random graph (infinite)
Suppose we have some method of generating sequences of letters from so that at each generation the probability of obtaining is , a real number strictly between and .
Let be a set of vertices. For each , we construct a graph on the vertices recursively.
is the unique graph on one vertex.
For we must describe for any when and are joined.
If then join and in iff and are joined in
If then generate a letter with . Join to iff .
Now let be the graph on so that for any , is joined to in iff it is in some .
Then we call a random graph. Consider the following property which we shall call f-saturation:
Given any finite disjoint and , subsets of there is some so that is joined to every point of and no points in .
A random graph has f-saturation with probability .
Proof: Let be an enumeration of . We say that is correctly joined to iff it is joined to all the members of and non of the members of . Then the probability that is not correctly joined is which is some real number strictly between and . The probability that none of the first are correctly joined is and the probability that none of the s are correctly joined is . Thus one of the s is correctly joined.
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.
- 1 Paul Erdős and Alfréd Rényi. Asymmetric graphs. Acta Math. Acad. Sci. Hung., 14:295–315, 1963.
|Title||random graph (infinite)|
|Date of creation||2013-03-22 13:32:18|
|Last modified on||2013-03-22 13:32:18|
|Last modified by||bbukh (348)|