uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Majority Bootstrap Percolation on G(n, p)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory. Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..
Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA..
Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1TN, England..
2017 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 1, P1.1Article in journal (Refereed) Published
Abstract [en]

Majority bootstrap percolation on a graph G is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have at least half of its neighbours infected become infected. We say that percolation occurs if eventually all vertices in G become infected. In this paper we provide sharp bounds for the critical size of the initially infected set in majority bootstrap percolation on the Erdos-Renyi random graph G(n,p). This answers an open question by Janson, Luczak, Turova and Vallier (2012). Our results obtained for p = clog(n)/n are close to the results obtained by Balogh, Bollobas and Morris (2009) for majority bootstrap percolation on the hypercube. We conjecture that similar results will be true for all regular-like graphs with the same density and sufficiently strong expansion properties.

Place, publisher, year, edition, pages
2017. Vol. 24, no 1, P1.1
Keyword [en]
bootstrap percolation, Erdos-Renyi random graph, threshold
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-316026ISI: 000392293400001OAI: oai:DiVA.org:uu-316026DiVA: diva2:1076918
Funder
Swedish Research Council
Available from: 2017-02-24 Created: 2017-02-24 Last updated: 2017-02-24Bibliographically approved

Open Access in DiVA

No full text

Other links

Fulltext

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Analysis and Probability Theory
In the same journal
The Electronic Journal of Combinatorics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf