On the maximum running time in graph bootstrap percolation

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

cellular automata extremal combinatorics weak saturation bootstrap percolation monotone cellular automata

Cellular automata (computational aspects) (68Q80) Extremal combinatorics (05D99)

Abstract: Graph bootstrap percolation is a simple cellular automaton introduced by Bollob'as in 1968. Given a graph

H

and a set

G s u b s e t e q E (K_{n})

we initially "infect" all edges in

G

and then, in consecutive steps, we infect every

e i n K_{n}

that completes a new infected copy of

H

in

K_{n}

. We say that

G

percolates if eventually every edge in

K_{n}

is infected. The extremal question about the size of the smallest percolating sets when

H = K_{r}

was answered independently by Alon, Kalai and Frankl. Here we consider a different question raised more recently by Bollob'as: what is the maximum time the process can run before it stabilizes? It is an easy observation that for

r = 3

this maximum is

l c e i l l o g_{2} (n - 1) c e i l

. However, a new phenomenon occurs for

r = 4

when, as we show, the maximum time of the process is

n - 3

. For

r g e q 5

the behaviour of the dynamics is even more complex, which we demonstrate by showing that the

K_{r}

-bootstrap process can run for at least

n^{2 - v a r e p s i l o n_{r}}

time steps for some

v a r e p s i l o n_{r}

that tends to

0

as

r o i n f t y

.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: On the maximum running time in graph bootstrap percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528995)