{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:59Z","timestamp":1760202779550},"reference-count":40,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2018,10,29]],"date-time":"2018-10-29T00:00:00Z","timestamp":1540771200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M011771\/1"],"award-info":[{"award-number":["EP\/M011771\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p>We study the following bootstrap percolation process: given a connected graph <jats:italic>G<\/jats:italic>, a constant <jats:italic>\u03c1<\/jats:italic>\u2009\u2208\u2009[0,1] and an initial set <jats:italic>A<\/jats:italic>\u2286<jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>) of <jats:italic>infected<\/jats:italic> vertices, at each step a vertex\u00a0<jats:italic>v<\/jats:italic> becomes infected if at least a <jats:italic>\u03c1<\/jats:italic>\u2010proportion of its neighbors are already infected (once infected, a vertex remains infected forever). Our focus is on the size <jats:italic>h<\/jats:italic><jats:sub><jats:italic>\u03c1<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) of a smallest initial set which is <jats:italic>contagious<\/jats:italic>, meaning that this process results in the infection of every vertex of <jats:italic>G<\/jats:italic>. Our main result states that every connected graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices has <jats:italic>h<\/jats:italic><jats:sub><jats:italic>\u03c1<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>)\u2009&lt;\u20092<jats:italic>\u03c1n<\/jats:italic> or <jats:italic>h<\/jats:italic><jats:sub><jats:italic>\u03c1<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>)\u2009=\u20091 (note that allowing the latter possibility is necessary because of the case <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20818-math-0001.png\" xlink:title=\"urn:x-wiley:rsa:media:rsa20818:rsa20818-math-0001\" \/>, as every contagious set has size at least one). This is the best\u2010possible bound of this form, and improves on previous results of Chang and Lyuu and of Gentner and Rautenbach. We also provide a stronger bound for graphs of girth at least five and sufficiently small <jats:italic>\u03c1<\/jats:italic>, which is asymptotically best\u2010possible.<\/jats:p>","DOI":"10.1002\/rsa.20818","type":"journal-article","created":{"date-parts":[[2018,10,29]],"date-time":"2018-10-29T17:52:33Z","timestamp":1540835553000},"page":"638-651","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Contagious sets in a degree\u2010proportional bootstrap percolation process"],"prefix":"10.1002","volume":"53","author":[{"given":"Frederik","family":"Garbe","sequence":"first","affiliation":[{"name":"Institute of Mathematics Czech Academy of Sciences \u017ditn\u00e1 25, 110 00, Prague Czech Republic"}]},{"given":"Richard","family":"Mycroft","sequence":"additional","affiliation":[{"name":"School of Mathematics University of Birmingham Birmingham UK"}]},{"given":"Andrew","family":"McDowell","sequence":"additional","affiliation":[{"name":"Informatics Department King's College London London UK"}]}],"member":"311","published-online":{"date-parts":[[2018,10,29]]},"reference":[{"key":"e_1_2_5_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.021"},{"key":"e_1_2_5_3_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/21\/19\/017"},{"key":"e_1_2_5_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_34"},{"key":"e_1_2_5_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-0946-6"},{"key":"e_1_2_5_6_1","unstructured":"O.AngelandB.Kolesnik. Minimal contagious sets in random graphs. arXiv: 1705.06815."},{"key":"e_1_2_5_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0451-6"},{"key":"e_1_2_5_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05552-2"},{"key":"e_1_2_5_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AOP433"},{"key":"e_1_2_5_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009322"},{"key":"e_1_2_5_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000271"},{"key":"e_1_2_5_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.03.005"},{"key":"e_1_2_5_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<409::AID-RSA11>3.0.CO;2-U"},{"key":"e_1_2_5_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20158"},{"key":"e_1_2_5_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2045"},{"key":"e_1_2_5_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.38"},{"key":"e_1_2_5_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2006.06.018"},{"key":"e_1_2_5_18_1","doi-asserted-by":"publisher","DOI":"10.1086\/521848"},{"key":"e_1_2_5_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1022874817"},{"key":"e_1_2_5_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(02)00124-2"},{"key":"e_1_2_5_21_1","doi-asserted-by":"publisher","DOI":"10.1088\/0022-3719\/12\/1\/008"},{"key":"e_1_2_5_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.07.008"},{"key":"e_1_2_5_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.043"},{"key":"e_1_2_5_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.131"},{"key":"e_1_2_5_25_1","unstructured":"G.Cordasco L.Gargano M.Mecchia A.A. Rescigno andU.Vaccaro Discovering small target sets in social networks: A fast and effective algorithm. arXiv:1610.03721."},{"key":"e_1_2_5_26_1","unstructured":"M.Dairyko M.Ferrara B.Lidick\u00fd R. R.Martin F.Pfender andA. J.Uzzell Chv\u00e1tal\u2010type degree conditions for bootstrap percolation from small sets. arXiv: 1610.04499."},{"key":"e_1_2_5_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.09.012"},{"key":"e_1_2_5_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1254"},{"key":"e_1_2_5_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.07.011"},{"key":"e_1_2_5_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.12.028"},{"key":"e_1_2_5_31_1","doi-asserted-by":"publisher","DOI":"10.1086\/226707"},{"key":"e_1_2_5_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AAP996"},{"key":"e_1_2_5_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-010-0338-z"},{"key":"e_1_2_5_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-002-0239-x"},{"key":"e_1_2_5_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP822"},{"key":"e_1_2_5_36_1","unstructured":"Kang MandMakai T. A simple proof of almost percolation onGn p. arXiv: 1608.00800v1."},{"key":"e_1_2_5_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_5_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2017.11.018"},{"key":"e_1_2_5_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00043-2"},{"key":"e_1_2_5_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2012.01.016"},{"key":"e_1_2_5_41_1","first-page":"5766","article-title":"A simple model of global cascades on random networks","volume":"99","author":"Watts DJ.","year":"2002","journal-title":"Phys. Sci. Appl. Math."}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20818","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T18:23:45Z","timestamp":1693679025000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,29]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1002\/rsa.20818"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20818","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,29]]},"assertion":[{"value":"2017-09-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}