On the maximum running time in graph bootstrap percolation

zbMATH Open1361.05135arXiv1510.07096MaRDI QIDQ528995FDOQ528995

Julian Sahasrabudhe, Béla Bollobás, Oliver Riordan, Michał Przykucki

Publication date: 18 May 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Graph bootstrap percolation is a simple cellular automaton introduced by Bollob'as in 1968. Given a graph $H$ and a set $GsubseteqE(K_n)$ we initially "infect" all edges in $G$ and then, in consecutive steps, we infect every $ein{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 $lceillo{g}_2(n-1)ceil$. However, a new phenomenon occurs for $r=4$ when, as we show, the maximum time of the process is $n-3$. For $rgeq5$ 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-varepsilo{n}_r}$ time steps for some $varepsilo{n}_r$ that tends to $0$ as $roinfty$.

Full work available at URL: https://arxiv.org/abs/1510.07096

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

zbMATH Keywords

cellular automataextremal combinatoricsweak saturationbootstrap percolationmonotone cellular automata

Mathematics Subject Classification ID

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

Cites Work

• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• An extremal problem for two families of sets
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Proof of Straley's argument for bootstrap percolation.
• Random disease on the square grid
• Minimal percolating sets in bootstrap percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Title not available (Why is that?)
• Bootstrap percolation on the random regular graph
• An extremal problem for sets with applications to graph theory
• Title not available (Why is that?)
• Linear algebra and bootstrap percolation
• Graph bootstrap percolation
• Bootstrap percolation on Galton-Watson trees
• The time of graph bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube

Cited In (10)

• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On \(K_{2, t}\)-bootstrap percolation
• Maximal Spanning Time for Neighborhood Growth on the Hamming Plane
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Long running times for hypergraph bootstrap percolation
• On the running time of hypergraph bootstrap percolation
• Title not available (Why is that?)
• Transitive closure in a polluted environment
• The maximal running time of hypergraph bootstrap percolation
• Line Percolation in Finite Projective Planes

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)