Random Graphs (Erdős–Rényi)

The G(n,p) model: expected edges, expected degree, and thresholds.

The idea

The Erdős–Rényi model $G(n, p)$ is the standard method of choosing a graph at random, so that we can ask what a typical graph looks like rather than what one particular graph does. Fix $n$ labeled vertices. There are $\binom{n}{2}$ pairs of them, hence $\binom{n}{2}$ possible edges; include each edge with probability $p$, all $\binom{n}{2}$ decisions independent. $G(n, p)$ names the resulting distribution over all graphs on those $n$ vertices, not any one graph.

Expected counts in the model come from linearity of expectation. Write the count as a sum of indicators — random variables equal to $1$ when a specific event happens and $0$ otherwise. Linearity of expectation says the expectation of a sum equals the sum of the expectations, however the terms depend on one another. The number of edges is the sum, over all $\binom{n}{2}$ pairs, of an indicator with expectation $p$, so $\mathbb{E}[\#\text{edges}] = \binom{n}{2}p.$ The same computation counts triangles, isolated vertices, or any other feature of the model.

Ways to work on it

• Walkthrough. The model, expected edge count, and expected degree.
• Practice. Expected edges or expected degree in a random G(n,p).
• Hardest. Probability of a specific graph and a first-moment threshold.

Builds on

• Graph Connectivity
• Independence
• Markov's Inequality

Leads to

• Expander Mixing Lemma
• Lovász Local Lemma

Not sure where to start? Take the ten-question placement test.