Monotone coupling of the Erdős–Rényi random graph \(G(n,p)\)

We consider \(n\) vertices and connect each pair independently with probability \(p\).

Here, we simulate a monotone coupling: a uniform random variable \(U_{ij} \sim \mathrm{Uniform}(0,1)\) is sampled per every possible edge \(\{i,j\}\), and the edge is present whenever \(U_{ij} \leq p\). This way, increasing \(p\) can only add edges, never remove them.

In other words, this way of simulating/coupling allows to say that if \(p \leq p' \) then we have \[ G(n,p) \subseteq G(n,p')\] where containment means subgraph containment.

For this reason, it is a standard tool in the field. In particular it implies that any monotone graph property, e.g. being connected, has a probability that is non-decreasing in \(p\).

Instructions:

• Change \(p\) by moving the slider.
• Press [Resample] to for new \(U_{ij}\) values.