{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,4]],"date-time":"2025-10-04T14:26:02Z","timestamp":1759587962451},"reference-count":21,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T00:00:00Z","timestamp":1555372800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","award":["200021","143337"],"award-info":[{"award-number":["200021","143337"]}],"id":[{"id":"10.13039\/501100001711","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":[[2019,12]]},"abstract":"<jats:p>We study a variant of the classical bootstrap percolation process on Erd\u0151s R\u00e9nyi random graphs. The graphs we consider have<jats:italic>inhibitory vertices<\/jats:italic>obstructing the diffusion of activity and<jats:italic>excitatory vertices<\/jats:italic>facilitating it. We study both a<jats:italic>synchronous<\/jats:italic>and an<jats:italic>asynchronous<\/jats:italic>version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously.<\/jats:p>","DOI":"10.1002\/rsa.20854","type":"journal-article","created":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T06:46:49Z","timestamp":1555483609000},"page":"881-925","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Bootstrap percolation with inhibition"],"prefix":"10.1002","volume":"55","author":[{"given":"Hafsteinn","family":"Einarsson","sequence":"first","affiliation":[{"name":"Department of Computer Science ETH Zurich Zurich Switzerland"}]},{"given":"Johannes","family":"Lengler","sequence":"additional","affiliation":[{"name":"Department of Computer Science ETH Zurich Zurich Switzerland"}]},{"given":"Frank","family":"Mousset","sequence":"additional","affiliation":[{"name":"Department of Computer Science ETH Zurich Zurich Switzerland"}]},{"given":"Konstantinos","family":"Panagiotou","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Institute of Mathematics University of Munich Munich Germany"}]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[{"name":"Department of Computer Science ETH Zurich Zurich Switzerland"}]}],"member":"311","published-online":{"date-parts":[[2019,4,16]]},"reference":[{"key":"e_1_2_5_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/21\/19\/017"},{"key":"e_1_2_5_3_1","unstructured":"O.AngelandB.Kolesnik. Large deviations for subcritical bootstrap percolation on the random graph. arXiv: 1705.06815v2 [math.PR] 2018."},{"key":"e_1_2_5_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177705986"},{"key":"e_1_2_5_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05552-2"},{"key":"e_1_2_5_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007619"},{"key":"e_1_2_5_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20158"},{"key":"e_1_2_5_8_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrn3136"},{"key":"e_1_2_5_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/0022-3719\/12\/1\/008"},{"key":"e_1_2_5_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1254"},{"key":"e_1_2_5_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02181252"},{"key":"e_1_2_5_12_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572213.001.0001","volume-title":"One Thousand Exercises in Probability","author":"Grimmett G.","year":"2001"},{"key":"e_1_2_5_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0952523800009640"},{"issue":"1","key":"e_1_2_5_14_1","first-page":"10","article-title":"Astonishing cellular automata","volume":"13","author":"Holroyd A.","year":"2007","journal-title":"Bull. Centre Rech. Math."},{"key":"e_1_2_5_15_1","unstructured":"S.Janson R.Kozma M.Ruszink\u00f3 andY.Sokolov. A modified bootstrap percolation on a random graph coupled with a lattice. arXiv: 1507.07997 [math.CO] 2015."},{"key":"e_1_2_5_16_1","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718.scard","volume-title":"Wiley\u2010Interscience Series in Discrete Mathematics and Optimization","author":"Janson S.","year":"2000"},{"key":"e_1_2_5_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP822"},{"key":"e_1_2_5_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_55"},{"key":"e_1_2_5_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/12087222X"},{"key":"e_1_2_5_20_1","doi-asserted-by":"publisher","DOI":"10.1523\/JNEUROSCI.1237-11.2011"},{"key":"e_1_2_5_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuron.2010.04.009"},{"key":"e_1_2_5_22_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989923"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20854","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20854","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.20854","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T23:38:45Z","timestamp":1721173125000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20854"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,16]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1002\/rsa.20854"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20854","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,16]]},"assertion":[{"value":"2017-01-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}