{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T17:29:06Z","timestamp":1790702946500,"version":"4.1.0"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>In an Achlioptas process two random pairs of $\\{1,\\dots,n\\}$ arrive in each round and the player has to choose one of them. We study the very restrictive version where a player's decisions cannot depend on the previous history and only one vertex from the two random edges is revealed. We prove that the player can create a giant component in $(2\\sqrt{5}-4+o(1))n=(0.4721\\ldots+o(1))n$ rounds and that this is the best possible. On the other hand, if the player wants to delay the appearance of a giant, then the optimal bound is $(1\/2+o(1))n$, the same as in the Erd\u0151s\u2013R\u00e9nyi model.<\/jats:p>","DOI":"10.1137\/070684148","type":"journal-article","created":{"date-parts":[[2009,5,20]],"date-time":"2009-05-20T18:27:35Z","timestamp":1242844055000},"page":"993-1008","source":"Crossref","is-referenced-by-count":5,"title":["Memoryless Rules for Achlioptas Processes"],"prefix":"10.1137","volume":"23","author":[{"given":"Andrew","family":"Beveridge","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom","family":"Bohman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oleg","family":"Pikhurko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,5,20]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon,\n                      A note on network reliability\n                      , in Discrete Probability and Algorithms, IMA Vol. Math. Appl. 72, Springer-Verlag, New York, 1995, pp. 11\u201314.","DOI":"10.1007\/978-1-4612-0801-3_2"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"K. B. Athreya and P. E. Ney,\n                      Branching Processes\n                      , Springer-Verlag, New York, 1972.","DOI":"10.1007\/978-3-642-65371-1"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-07-08853-3"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1019"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20038"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20085"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007486"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20168"},{"key":"R9","unstructured":"R. Durrett,\n                      Probability: Theory and Examples\n                      , 2nd ed., Duxbury Press, Belmont, CA, 1996."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Flaxman, D. Gamarnik, and G. B. Sorkin,\n                      Embracing the giant component\n                      , in LATIN 2004: Theoretical Informatics, M. Farach-Coltin, ed., Springer-Verlag, Berlin, 2004, pp. 69\u201379.","DOI":"10.1007\/978-3-540-24698-5_11"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.66.066121"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2163-2"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070684148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:52Z","timestamp":1787322892000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070684148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070684148"],"URL":"https:\/\/doi.org\/10.1137\/070684148","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}