# 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 %}
