> For the complete documentation index, see [llms.txt](https://aparande.gitbook.io/berkeley-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aparande.gitbook.io/berkeley-notes/eecs126-0/eecs126-6.md).

# Random Graphs

A random graph is one which is generated through some amount of randomness.

{% hint style="info" %}

## Definition 76

An Erdos-Renyi random graph $$G(n, p)$$ is an undirected graph on $$n \geq 1$$ vertices where each edge exists independently with probability $$p$$.
{% endhint %}

With random graphs, we often ask what happens to particular properties as $$n\to\infty$$ and $$p$$ scales with some relationship to $$n$$. In particular, we want that property to hold with high probability (i.e, as $$n\to\infty$$, the probabilty that $$G(n,p)$$ has the property approaches 1).

{% hint style="info" %}

## Theorem 42

Every monotone graph property (adding more edges doesn't delete the property) has a sharp threshold $$t\_n$$ where if $$p \gg t\_n$$, then $$G(n, p)$$ has $$p$$ with high probability and does not have $$p$$ with high probability if $$t\_n \ll G(n,p)$$.
{% endhint %}

One example of a threshold is the connectivity threshold.

{% hint style="info" %}

## Theorem 43 (Erdos-Renyi Connectivity Theorem) <a href="#theorem-43" id="theorem-43"></a>

Fix $$\lambda > 0$$ and let $$p\_n = \lambda \frac{\log n}{n}$$. If $$\lambda > 1$$, then $$P(G(n,p\_n)\text{ is connected})$$ with probability approaching 1, and if $$\lambda < 1$$, then $$P(G(n,p\_n)\text{ is disconnected})$$with probability approaching 1
{% endhint %}