{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,21]],"date-time":"2026-06-21T07:48:48Z","timestamp":1782028128835,"version":"3.54.5"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,5,28]],"date-time":"2014-05-28T00:00:00Z","timestamp":1401235200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>Bounded-size rules (BSRs) are dynamic random graph processes which incorporate limited choice along with randomness in the evolution of the system. Typically one starts with the empty graph and at each stage two edges are chosen uniformly at random. One of the two edges is then placed into the system according to a decision rule based on the sizes of the components containing the four vertices. For bounded-size rules, all components of size greater than some fixed <jats:italic>K<\/jats:italic> \u2265 1 are accorded the same treatment. Writing <jats:bold>BSR<\/jats:bold>(<jats:italic>t<\/jats:italic>) for the state of the system with \u230a<jats:italic>nt<\/jats:italic>\/2\u230b edges, Spencer and Wormald [26] proved that for such rules, there exists a (rule-dependent) critical time <jats:italic>t<jats:sub>c<\/jats:sub><\/jats:italic> such that when <jats:italic>t<\/jats:italic> &lt; <jats:italic>t<jats:sub>c<\/jats:sub><\/jats:italic> the size of the largest component is of order log <jats:italic>n<\/jats:italic>, while for <jats:italic>t<\/jats:italic> &gt; <jats:italic>t<jats:sub>c<\/jats:sub><\/jats:italic>, the size of the largest component is of order <jats:italic>n<\/jats:italic>. In this work we obtain upper bounds (that hold with high probability) of order <jats:italic>n<\/jats:italic><jats:sup>2\u03b3<\/jats:sup> log<jats:sup>4<\/jats:sup><jats:italic>n<\/jats:italic>, on the size of the largest component, at time instants <jats:italic>t<jats:sub>n<\/jats:sub><\/jats:italic> = <jats:italic>t<jats:sub>c<\/jats:sub><\/jats:italic>\u2212<jats:italic>n<\/jats:italic><jats:sup>\u2212\u03b3<\/jats:sup>, where \u03b3 \u2208 (0,1\/4). This result for the barely subcritical regime forms a key ingredient in the study undertaken in [4], of the asymptotic dynamic behaviour of the process describing the vector of component sizes and associated complexity of the components for such random graph models in the critical scaling window. The proof uses a coupling of BSR processes with a certain family of inhomogeneous random graphs with vertices in the type space <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000261_inline1\"\/><jats:tex-math>$\\mathbb{R}_+\\times \\mathcal{D}([0,\\infty):\\mathbb{N}_0)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000261_inline2\"\/><jats:tex-math>$\\mathcal{D}([0,\\infty):\\mathbb{N}_0)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the Skorokhod <jats:italic>D<\/jats:italic>-space of functions that are right continuous and have left limits, with values in the space of non-negative integers <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000261_inline3\"\/><jats:tex-math>$\\mathbb{N}_0$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, equipped with the usual Skorokhod topology. The coupling construction also gives an alternative characterization (from the usual explosion time of the susceptibility function) of the critical time <jats:italic>t<jats:sub>c<\/jats:sub><\/jats:italic> for the emergence of the giant component in terms of the operator norm of integral operators on certain <jats:italic>L<\/jats:italic><jats:sup>2<\/jats:sup> spaces.<\/jats:p>","DOI":"10.1017\/s0963548314000261","type":"journal-article","created":{"date-parts":[[2014,5,28]],"date-time":"2014-05-28T09:09:44Z","timestamp":1401268184000},"page":"505-538","source":"Crossref","is-referenced-by-count":5,"title":["Bounded-Size Rules: The Barely Subcritical Regime"],"prefix":"10.1017","volume":"23","author":[{"given":"SHANKAR","family":"BHAMIDI","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"AMARJIT","family":"BUDHIRAJA","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"XUAN","family":"WANG","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,5,28]]},"reference":[{"key":"S0963548314000261_ref25","unstructured":"Sen S. (2013) On the largest component in the subcritical regime of the Bohman\u2013Frieze process. arXiv:1307.2041"},{"key":"S0963548314000261_ref13","unstructured":"van der Hofstad R. and Nachmias A. (2012) Hypercube percolation. arXiv:1201.3953. To appear in Metrika."},{"key":"S0963548314000261_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP647"},{"key":"S0963548314000261_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9477-8"},{"key":"S0963548314000261_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548314000261_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20038"},{"key":"S0963548314000261_ref23","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP798"},{"key":"S0963548314000261_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s11512-011-0157-1"},{"key":"S0963548314000261_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-2438-3"},{"key":"S0963548314000261_ref12","first-page":"343","article-title":"On the evolution of random graphs.","volume":"38","author":"Erd\u0151s","year":"1961","journal-title":"Bull. Inst. Internat. Statist."},{"key":"S0963548314000261_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1019"},{"key":"S0963548314000261_ref3","doi-asserted-by":"crossref","unstructured":"Bhamidi S. , Budhiraja A. and Wang X. (2013) Aggregation models with limited choice and the multiplicative coalescent. Random Struct. Alg. http:\/\/dx.doi.org\/10.1002\/rsa.20493","DOI":"10.1002\/rsa.20493"},{"key":"S0963548314000261_ref24","article-title":"The evolution of subcritical Achlioptas processes","author":"Riordan","year":"2014","journal-title":"Random Struct. Alg."},{"key":"S0963548314000261_ref2","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1214\/aop\/1024404421","article-title":"Brownian excursions, critical random graphs and the multiplicative coalescent.","volume":"25","author":"Aldous","year":"1997","journal-title":"Ann. Probab."},{"key":"S0963548314000261_ref1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1167782"},{"key":"S0963548314000261_ref19","first-page":"873","volume-title":"Proc. International Congress of Mathematicians","author":"Kim","year":"2006"},{"key":"S0963548314000261_ref15","doi-asserted-by":"publisher","DOI":"10.1063\/1.2982848"},{"key":"S0963548314000261_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20168"},{"key":"S0963548314000261_ref14","doi-asserted-by":"publisher","DOI":"10.1214\/07-AAP490"},{"key":"S0963548314000261_ref21","volume-title":"Markov Chains","author":"Norris","year":"1998"},{"key":"S0963548314000261_ref11","first-page":"17","article-title":"On the evolution of random graphs.","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl."},{"key":"S0963548314000261_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2163-2"},{"key":"S0963548314000261_ref17","first-page":"231","article-title":"The birth of the giant component (with an introduction by the editors).","volume":"4","author":"Janson","year":"1994","journal-title":"Random Struct. Alg."},{"key":"S0963548314000261_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20437"},{"key":"S0963548314000261_ref22","doi-asserted-by":"publisher","DOI":"10.1214\/07-AAP493"},{"key":"S0963548314000261_ref4","first-page":"1","article-title":"The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs","author":"Bhamidi","year":"2013","journal-title":"Probab Theory Rel. Fields"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T23:13:05Z","timestamp":1555888385000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000261\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,28]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["S0963548314000261"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000261","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,28]]}}}