How to Get the Random Graph with Non-Uniform Probabilities?
Leonardo N. Coregliano, Jarosław Swaczyna, Agnieszka Widz · The Electronic Journal of Combinatorics · 2025
The Rado Graph, sometimes also known as the (countable) Random Graph, can be generated almost surely by putting an edge between any pair of vertices with some fixed probability $p\in(0,1)$, independently of other pairs. In this article, we study the influence of allowing different probabilities for each pair of vertices. More specifically, we characterize for which sequences $(p_n)_{n\in \mathbb{N}}$ of values in $[0,1]$ there exists a bijection $f$ from pairs of vertices in $\mathbb{N}$ to $\mathbb{N}$ such that if we put an edge between $v$ and $w$ with probability $p_{f(\{v,w\})}$, independently of other pairs, then the Random Graph arises almost surely.