DROPS

Document

Keynote Speakers

DOI: 10.4230/LIPIcs.AofA.2018.4

Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers)

Authors: Karen Gunderson

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

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.

Cite as

Karen Gunderson. Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gunderson:LIPIcs.AofA.2018.4,
  author =	{Gunderson, Karen},
  title =	{{Bootstrap Percolation and Galton-Watson Trees}},
  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 =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.4},
  URN =		{urn:nbn:de:0030-drops-88977},
  doi =		{10.4230/LIPIcs.AofA.2018.4},
  annote =	{Keywords: bootstrap percolation, Galton-Watson trees}
}

Search Results

Documents authored by Gunderson, Karen

Bootstrap Percolation and Galton-Watson Trees (Keynote Speakers)

Abstract

Cite as

Thanks for your feedback!

Could not send message