Giant Component and Phase Transition

Status: placeholder — write lecture notes here before teaching.

Goals¶

• Branching-process intuition for component sizes

• The critical threshold $p = 1/n$

• Emergence of a giant component

• Connectivity and cycles at a high level

Outline¶

1. Component of a vertex as a branching process

2. Supercritical vs subcritical regimes

3. Phase transition in $G(n,p)$

4. Small World (Watts–Strogatz) as a brief survey

Sources¶

• Blum, Hopcroft, Kannan, Foundations of Data Science, Ch. 7–8