Journal article icon

Journal article

On the maximum running time in graph bootstrap percolation

Abstract:

Graph bootstrap percolation is a simple cellular automaton introduced by Bollob´as in 1968. Given a graph H and a set G ⊆ E(Kn) we initially “infect” all edges in G and then, in consecutive steps, we infect every e ∈ Kn that completes a new infected copy of H in Kn. We say that G percolates if eventually every edge in Kn is infected. The extremal question about the size of the smallest percolating sets when H = Kr was answered independently by Alon, Kalai and Frankl. Here we consider a differ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Role:
Author
More from this funder
Grant:
MULTIPLEX grant 317532
Publisher:
Electronic Journal of Combinatorics Publisher's website
Journal:
Electronic Journal of Combinatorics Journal website
Volume:
24
Issue:
2
Pages:
P2.16
Publication date:
2017-05-05
Acceptance date:
2017-01-01
EISSN:
1077-8926
ISSN:
1077-8926
URN:
uuid:17b69740-0d82-4ebd-b5ed-0400419f305b
Source identifiers:
572423
Local pid:
pubs:572423
Paper number:
2

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP