Percolation theory

• Percolation theory relates to how networks/graphs behave when edges or vertices are removed from the system
• Representative question:
  • “given that a liquid is poured onto some porous material, will the liquid be able to make its way from hole to hole and reach the bottom?”
  • often modeled as a 3-dimensional Graph of size n x n x n, where edges (bonds) between vertices (sites) allow the liquid to pass through probabilistically
    • edges will independently allow liquid between two given vertices with probability p, or not with probability 1 - p
    • so the likelihood of percolation depends on the “site vacancy probability” p
      • “therefore, for a given p, what is the probability that an open path exists for the liquid?”
        • particularly when n (the dimension of the porous material) is large
• a system “percolates” if and only if (iff) there is an open path from top to bottom
• reflected in many real-world systems: