Is it possible to construct the Rado Graph as a countably infinite graph with non-constant edge probabilities?

Question

Let's say we have a countably infinite set $V$ of vertices and a map $f:V\times{V}\to{(0,1)}$ that assigns to each pair $(i,j)$ of vertices an edge with probability $f(i,j) = p$. I believe that if the function $f$ is constant for all pairs $(i,j)$ then the result is the Rado Graph, but I would like to know under what conditions that remains the case if we allow $f$ to be non-constant.

Answer 1

It is enough that the edge probabilities be bounded away from $0$ and $1$. By this I mean that there is a number $d > 0$ for which all probabilities are between $d$ and $1-d$.

Fagin's proof that Gaifman's axioms for the theory of the Rado graph have probability $1$ is written for $p=1/2$ but continues to work for bounded edge probabilities.

http://researcher.ibm.com/researcher/files/us-fagin/jsl76.pdf

See the last few lines of the proof of theorem 2 and notice that the assumption $p=1/2$ isn't needed, only that $p^m$ (or in your case $p_1 p_2 \cdots p_m$) for constant $m$ is not $1$. (He must also use somewhere that it is not $0$ but I don't see the exact line in the paper where that is implicit. )

Answer 2

To complement zyx's answer, it is possible to construct the Rado graph in a purely deterministic fashion. In practice it gives you a function $f(x,y)\in\{0,1\}$ (so in particular non-constant). You can find this function in the wikipedia article on the Rado graph: https://en.wikipedia.org/wiki/Rado_graph