k-vertex rule percolation process

guillefix 4th November 2016 at 2:43pm

An Explosive percolation process that is based on chosing kk vertices at random and adding edges among those vertices according to some rule.

kk-vertex rules are actually a generalization of mm-edge rules (aka Achlioptas process) because a mm-edge rule can be constructed from a nn-vertex rule, where n2mn \geq 2m, which chooses n2mn\geq 2m vertices at random (possibly repeating, but still being able to have mm distinct edges), and then choose mm edges at random within these 2m2m vertices. Note that we need n2mn\geq 2m so that we don't restrict the chosen edges to have some vertex in common.

mm-vertex rule (as defined here): In processes following an mm-vertex rule, the agent is presented with the random list (set) vmv_m of vertices, and, unless two or more are already in the same component, must add one or more edges between them, according to any deterministic or random rule that depends only on the history.

Some kk-vertex rules are examples of Non-self-averaging percolation process, showing novel supercritical phenomena, like stochastic staircases!

In Achlioptas process phase transitions are continuous, it was shown that the Percolation phase transition for processes following a vertex rule was continuous. However, they can still show some discontinuity arbitrarily close to the critical point (see Non-self-averaging percolation process).