Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the meaning of the term "edge percolation"?

Context is graph theory, specifically, random graphs. In general, what does "percolation" mean in the context of random graphs?

Thanks.

share|improve this question
2  
    
@QiaochuYuan thanks. I saw the Percolation page at wikipedia, but wasn't aware of the "Percolation Theory" page. –  becko May 11 '12 at 16:55
    
@QiaochuYuan If you want, you should add that link, and perhaps some comments, as an answer, so I can accept it. –  becko May 12 '12 at 6:25

1 Answer 1

up vote 2 down vote accepted

Edge percolation (often called bond percolation) refers to edges being randomly removed from a graph (a lattice): typically, each edge has probability $p\in (0,1)$ of surviving, independent of other edges. In line with original meaning of percolation (fluid transit), one may think of the removed edges as closed, i.e., made impermeable. How far the fluid may spread in the graph depends on the size of connected component. One often sees a phase transition: emergence of a unique giant component when $p$ exceeds some value $p_0$.

Some references: Wikipedia page, Pierre Nolin's lecture slides.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.