License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.4
URN: urn:nbn:de:0030-drops-88977
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8897/
Go to the corresponding LIPIcs Volume Portal

Gunderson, Karen

Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers)

pdf-format:
LIPIcs-AofA-2018-4.pdf (0.2 MB)

Abstract

A bootstrap process is a type of cellular automaton, acting on the vertices of a graph which are in one of two states: `healthy' or `infected'. For any positive integer r, the r-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least r infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected. For an infinite graph, of interest is the random setting, in which each vertex is initially infected independently with a fixed probability. I will give some history of this process for infinite trees and present results on the possible values of critical probabilities for percolation on Galton-Watson trees.
This talk is based on joint work with Bollobás, Holmgren, Janson, and Przykucki.

BibTeX - Entry

@InProceedings{gunderson:LIPIcs:2018:8897,
  author =	{Karen Gunderson},
  title =	{{Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers)}},
  booktitle =	{29th International Conference on Probabilistic,  Combinatorial and Asymptotic Methods for the Analysis of Algorithms  (AofA 2018)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8897},
  URN =		{urn:nbn:de:0030-drops-88977},
  doi =		{10.4230/LIPIcs.AofA.2018.4},
  annote =	{Keywords: bootstrap percolation, Galton-Watson trees}
}

Keywords: bootstrap percolation, Galton-Watson trees
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI