{"entities":{"Q1688015":{"pageid":1698756,"ns":120,"title":"Item:Q1688015","lastrevid":57461769,"modified":"2026-03-31T00:43:06Z","type":"item","id":"Q1688015","labels":{"en":{"language":"en","value":"Contagious sets in random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6822203"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$C8E04167-8CAC-4FF9-A12B-E8A8B0BE14E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"61a62fcb921cbef95299cfc14ccf5e5392ef1a30","datavalue":{"value":{"text":"Contagious sets in random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1688015$18684DE9-AFEF-4565-9DED-8ABEBD7B0033","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3998f0b9d4e0c639664eba77afbd6676fc0dd177","datavalue":{"value":"1387.05233","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1688015$12FA7A11-38AE-4753-8E46-4F0645D9FBAE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d96e435c8e10425897a74554f6c52502db94165a","datavalue":{"value":"10.1214/16-AAP1254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1688015$2869DDA8-886D-47BD-B303-9E2104D5B143","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$480DC6BF-0EEE-4E53-8262-E60CE1544477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25c2ebd3ef5ed7e34207dd3c09ff9305fad21ac1","datavalue":{"value":{"entity-type":"item","numeric-id":418890,"id":"Q418890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$585575D9-26F1-483F-B319-13B8053E7E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4fbe35cb61496fa8363dcdb2d9d3a4d54bbef6e2","datavalue":{"value":{"entity-type":"item","numeric-id":6480586,"id":"Q6480586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$13FD4294-46F5-429C-81C7-730E28F73B8A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e04a4b352e727282a8f30f5809a3df145fda07dd","datavalue":{"value":{"entity-type":"item","numeric-id":81240,"id":"Q81240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$FEAC4F37-FD33-4125-BCCA-533AED66FDB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7600255b4ee907c1b1dfbc5f62c7b1165ab1b6d0","datavalue":{"value":{"time":"+2018-01-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1688015$5FAAEB26-1870-4E92-A750-98DF681063A8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f4e65c4ef58bd6ae06abce871552976729777cb","datavalue":{"value":"https://arxiv.org/abs/1602.01751","type":"string"},"datatype":"url"},"type":"statement","id":"Q1688015$FC377608-D174-4204-811C-5CAEBE6EEE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ccfc29e8d3bae0370da7a389dab2b2fbc5157a31","datavalue":{"value":"https://projecteuclid.org/euclid.aoap/1509696032","type":"string"},"datatype":"url"},"type":"statement","id":"Q1688015$2420BB62-D7A0-43BF-A210-FB5DCECB9863","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"837dfd343427faed6f9d24ceab34c4f0932c763a","datavalue":{"value":"The authors consider the classical bootstrap percolation process on a binomial random graph \\(G(n,p)\\). A set of vertices is called contagious, if the bootstrap process percolates when this set is the set of initially active vertices. The authors of this paper consider the typical size of a smallest percolating set in a \\(G(n,p)\\) random graph. Expressing \\(p=d/n\\), they give the typical order of magnitude of a smallest contagious set in \\(G(n,d/n)\\), for \\(d\\gg 1\\) but \\(d\\) growing at most like a polynomial of order \\(n^{(r-1)/r}\\) (together with some logarithmic factors), where \\(r\\) is the activation parameter of the bootstrap process. They also consider the question about when this minimum size of a contagious set could be equal to \\(r\\), that is, there exists a set of only \\(r\\) vertices such that if only these are active in the beginning of the process, then it percolates. They give the critical function \\(p^\\ast=p^\\ast(n)\\) (up to multiplicative constants) such that when \\(p \\gg p^\\ast\\), then such a set of size \\(r\\) exists, but when \\(p\\ll p^\\ast\\), it does not.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1688015$3AC83D11-9FA1-4856-A372-1F955150E2AB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee5ba7f50bd271f0d45cb8360d5c0d385d238ae","datavalue":{"value":{"entity-type":"item","numeric-id":490411,"id":"Q490411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$6A0E86DD-0AD3-4377-BBCC-6696B7F74403","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1688015$381962FB-3A4C-4ADD-934A-9D2FCBE28710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7fdc23c20020356aaedd36d12d09aa94bd3b098e","datavalue":{"value":"60K35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1688015$12C6F4CB-6251-4508-9FCA-E7E09889BC36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1688015$3674974F-4EC7-4E08-901E-DF062179D3DD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"473964466681d887356a840aeb7ce5d23c6acb9b","datavalue":{"value":"6822203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1688015$0B35389C-246B-493B-8D4B-CDF52F329963","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"111f0cf4eb6ef141ce242ef7b09b57abb2506426","datavalue":{"value":"bootstrap percolation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1688015$DFFA4BB9-395F-42E9-A59A-443767BB2D96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1688015$672F475E-A223-4649-809D-3383D445A704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7cd36eaf13938d2519d1d068580c3a024ffcc5a","datavalue":{"value":"contagious sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1688015$763EB1DF-5616-476E-AA8E-17D73C59727C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aeae640a2ee655870ff07a4c143c20a6e0535e89","datavalue":{"value":"minimum contagious set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1688015$EFB39422-F39A-46A9-92E8-0B93AB8945D9","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1688015$E630643E-E977-477A-8F98-D0A539BD7525","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c3538e14a06c091ed09f542994bb36fe8c93d13","datavalue":{"value":{"entity-type":"item","numeric-id":5363074,"id":"Q5363074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad68b082a6eef9b7353a25ce09177ff0ae63cf87","datavalue":{"value":{"amount":"+0.8777284026145935","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1688015$7D2E1734-440F-4D76-B93D-F1156DAFC62A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fadaf06393f2d797f972f24d1f945425ed3983b","datavalue":{"value":{"entity-type":"item","numeric-id":418891,"id":"Q418891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02a87612836b4cce2cea02c38b048f753df49d88","datavalue":{"value":{"amount":"+0.864997386932373","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1688015$D10D14FB-2981-4769-8F9A-8E61845B37F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cab4fc78a6cb1f80e909d08f9baed69cf7b74b","datavalue":{"value":{"entity-type":"item","numeric-id":1650097,"id":"Q1650097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24f227e5558fcdf0b864e0bd06faf1945b546713","datavalue":{"value":{"amount":"+0.8344348669052124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1688015$D134130D-3C5C-468D-83D6-EEA8EE4157FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1688015","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1688015"}}}}}