# 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 $\{a_{i}:i<\omega\}$ be a set of vertices. For each $i<\omega$ , $i\geq 1$ we construct a graph $G_{i}$ on the vertices $a_{1},\ldots,a_{i}$ recursively.

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

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

• If $k then join $a_{j}$ and $a_{k}$ in $G_{i}$ iff $a_{j}$ and $a_{k}$ are joined in $G_{i-1}$

• 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 $\Gamma$ be the graph on $\{a_{i}:i<\omega\}$ so that for any $n,m<\omega$, $a_{n}$ is joined to $a_{m}$ in $\Gamma$ iff it is in some $G_{i}$.

Then we call $\Gamma$ a random graph  . Consider the following property which we shall call f-saturation:

Given any finite disjoint $U$ and $V$, subsets of $\{a_{i}:i<\omega\}$ there is some $a_{n}\in\{a_{i}:i<\omega\}\setminus(U\cup V)$ so that $a_{n}$ 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 $b_{1},b_{2},\ldots,b_{n},\ldots$ be an enumeration of $\{a_{i}:i<\omega\}\setminus(U\cup V)$. 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|}(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 $y^{m}$ and the probability that none of the $b_{i}$s are correctly joined is $\textrm{lim}_{n\to\infty}y^{n}=0$. Thus one of the $b_{i}$s is correctly joined.

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.

## References

• 1 Paul Erdős and Alfréd Rényi. 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