Plan for today:

*The Big Picture & Short Recap*- §1 Motivation for random graphs
- §2 Erdős–Rényi random graph
- §3 Properties of $ER_n(\lambda / n)$ that are dicussed in chapter 4

*The supercritical regime of $ER_n(\lambda / n)$*- §4 Intuition
- §5 Law of large numbers
- §6 Central limit theorem
- §7$^{*}$ The discrete duality principle

- model large and complex networks using
- (1) local and (2) probabilistic rules
- lower conceptual overhead, "divide and conquer" principle
- give us the ability to describe complexity in nets

- (1) local and (2) probabilistic rules
- study properties of these models
- properties of large nets <-> limiting properties of their models
- thus, we consider graph sequences and study properties of their limits

- the simplest imaginable model of a random network
- it has a phase transition in the size of the maximal connected component (when p varies)
- simple but it still has some very interesting properties

- recall def. of $ER_n(p)$:
- $n$ vertices
- each pair of vertices is independently connected with a fixed prob. $p$

- hence, the degree of a vertex ~ $ Bin(n-1,p)$
- hereafter we consider $ER_n(\lambda / n)$ since:
- we want the expected degree $(n-1)p$ to be constant for large $n$
- i.e. with $p = \lambda / n$, we get $(n-1)p = \frac{(n-1)}{n} \lambda \approx \lambda$

- we study connected components / the largest connected component
- connected components can be described as branching processes
- B.P. have a phase transition
- expected offspring $E[X] < 1$, then $\eta =$ extinction prob. $=1$
- expected offspring $E[X] > 1$, then $\eta < 1$ i.e. the process survives with positive prob.

- B.P. have a phase transition

- connected components of $ER_n(\lambda / n)$ have a related phase transition
- the subcritical regime: expected degree $\approx \lambda < 1$
- connected components are small, the largest of order $log(n)$ i.e. we have $$ \frac{|C_{\text{max}}|}{log(n)} \xrightarrow[]{P} \frac{1}{I_{\lambda}}$$

- the supercritical regime: expected degree $\approx \lambda > 1$
- simulation last time -> there is one giant connected component
**Q:***what can we prove in this setting?*

- the subcritical regime: expected degree $\approx \lambda < 1$

-> Erdös-Rényi Random Graph, The supercritical regime notebook