random graph (infinite)
Suppose we have some method $M$ of generating sequences^{} 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 $$ be a set of vertices. For each $$ , $i\ge 1$ we construct a graph ${G}_{i}$ on the vertices ${a}_{1},\mathrm{\dots},{a}_{i}$ recursively.

•
${G}_{1}$ is the unique graph on one vertex.

•
For $i>1$ we must describe for any $$ when ${a}_{j}$ and ${a}_{k}$ are joined.

–
If $$ then join ${a}_{j}$ and ${a}_{k}$ in ${G}_{i}$ iff ${a}_{j}$ and ${a}_{k}$ are joined in ${G}_{i1}$

–
If $k=i$ then generate a letter $l(j,k)$ with $M$. Join ${a}_{j}$ to ${a}_{k}$ iff $l(j,k)=p$.

–
Now let $\mathrm{\Gamma}$ be the graph on $$ so that for any $$, ${a}_{n}$ is joined to ${a}_{m}$ in $\mathrm{\Gamma}$ iff it is in some ${G}_{i}$.
Then we call $\mathrm{\Gamma}$ a random graph^{}. Consider the following property which we shall call fsaturation:
Given any finite disjoint $U$ and $V$, subsets of $$ there is some $$ so that ${a}_{n}$ is joined to every point of $U$ and no points in $V$.
Proposition 1
A random graph has fsaturation with probability $\mathrm{1}$.
Proof: Let ${b}_{1},{b}_{2},\mathrm{\dots},{b}_{n},\mathrm{\dots}$ be an enumeration of $$. We say that ${b}_{i}$ 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 ${b}_{i}$ is not correctly joined is $(1{x}^{U}{(1x)}^{V})$ which is some real number $y$ strictly between $0$ and $1$. The probability that none of the first $m$ are correctly joined is ${y}^{m}$ and the probability that none of the ${b}_{i}$s are correctly joined is ${\text{lim}}_{n\to \mathrm{\infty}}{y}^{n}=0$. Thus one of the ${b}_{i}$s is correctly joined.
Proposition 2
Any two countable^{} graphs with fsaturation are isomorphic^{}.
Proof: This is via a back and forth argument. The property of fsaturation 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 homogeneous^{} and universal^{} for the class of all countable graphs.
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  20130322 13:32:18 
Last modified on  20130322 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 