Percolation theory

Summary

Percolation theory studies the connected clusters of a random subgraph of a large graph, where each edge or vertex is kept independently with probability $p$. Its main question is whether an infinite cluster appears. On many graphs there is a sharp percolation threshold: below it all clusters are finite, above it an infinite cluster exists. It is a basic model of a phase transition and of flow through a porous medium.