Strict majority bootstrap percolation on augmented rings, tori and random regular graphs.

Abstract:

We study the strict majority bootstrap percolation process
on graphs. Vertices may be active or passive. Initially, active vertices are
chosen independently with probability p. Each passive vertex v becomes
active if at least ceil((deg(v)+1)/2) of its neighbors are active (and thereafter
never changes its state). If at the end of the process all vertices become
active then we say that the initial set of active vertices percolates on the
graph. We address the problem of finding graphs for which percolation is
likely to occur for small values of p. We call p_c the least p which
makes percollation occur with probability 1/2.

For that purpose we study percolation on different topologies:

-Rings of length n augmented with a universal vertex. Also, each vertex v in the
ring is connected to all nodes whose distance to v is less than or equal to a
parameter r.

– n × n toroidal grids augmented similarly.

– Random regular graphs of even degree, also augmented
with a universal node.

For the augmented rings, a number of results can be obtained analytically.
In particular we know that, in an asymptotic sense, p_c=1/4. This is the
smallest p_c known so far.

In an attempt to find graphs with lower p_c, we computationally estimated the
percolation threshold for the other two families. The tori seem more promising,
with p_c<1/5. On the other hand, for the random regular graphs we obtained
unexpectedly large values for p_c.

Posted on Jun 6, 2014 in Discrete Mathematics, Seminars