Logo: to the web site of Uppsala University

uu.sePublikasjoner fra Uppsala universitet
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Majority Bootstrap Percolation on G(n, p)
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen, Analys och sannolikhetsteori. 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 (engelsk)Inngår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, nr 1, artikkel-id P1.1Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
2017. Vol. 24, nr 1, artikkel-id P1.1
Emneord [en]
bootstrap percolation, Erdos-Renyi random graph, threshold
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-316026ISI: 000392293400001OAI: oai:DiVA.org:uu-316026DiVA, id: diva2:1076918
Forskningsfinansiär
Swedish Research CouncilTilgjengelig fra: 2017-02-24 Laget: 2017-02-24 Sist oppdatert: 2017-11-29bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Fulltext

Person

Holmgren, Cecilia

Søk i DiVA

Av forfatter/redaktør
Holmgren, Cecilia
Av organisasjonen
I samme tidsskrift
The Electronic Journal of Combinatorics

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 435 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf