{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T10:10:12Z","timestamp":1721556612074},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"content-version":"unspecified","delay-in-days":24,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let<jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>M<\/jats:italic>) be a uniform random graph with<jats:italic>n<\/jats:italic>vertices and<jats:italic>M<\/jats:italic>edges. Let<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000154_inline1\"\/><jats:tex-math>${\\wp_{n,m}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>be the maximum block size of<jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>M<\/jats:italic>), that is, the maximum size of its maximal 2-connected induced subgraphs. We determine the expectation of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000154_inline2\"\/><jats:tex-math>${\\wp_{n,m}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>near the critical point<jats:italic>M<\/jats:italic>=<jats:italic>n<\/jats:italic>\/2. When<jats:italic>n<\/jats:italic>\u2212 2<jats:italic>M<\/jats:italic>\u226b<jats:italic>n<\/jats:italic><jats:sup>2\/3<\/jats:sup>, we find a constant<jats:italic>c<\/jats:italic><jats:sub>1<\/jats:sub>such that<jats:disp-formula id=\"S0963548319000154_dispu1\"><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548319000154_eqnu1\"\/><jats:tex-math>$$c_1 = \\lim_{n \\rightarrow \\infty} \\left({1 - \\frac{2M}{n}} \\right) \\,\\E({\\wp_{n,m}}).$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula>Inside the window of transition of<jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>M<\/jats:italic>) with<jats:italic>M<\/jats:italic>= (<jats:italic>n<\/jats:italic>\/2)(1 + \u03bb<jats:italic>n<\/jats:italic><jats:sup>\u22121\/3<\/jats:sup>), where \u03bb is any real number, we find an exact analytic expression for<jats:disp-formula id=\"S0963548319000154_dispu2\"><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548319000154_eqnu2\"\/><jats:tex-math>$$c_2(\\lambda) = \\lim_{n \\rightarrow \\infty} \\frac{\\E{\\left({\\wp_{n,{{(n\/2)}({1+\\lambda n^{-1\/3}})}}}\\right)}}{n^{1\/3}}.$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula>This study relies on the symbolic method and analytic tools from generating function theory, which enable us to describe the evolution of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000154_inline3\"\/><jats:tex-math>$n^{-1\/3}\\,\\E{\\left({\\wp_{n,{{(n\/2)}({1+\\lambda n^{-1\/3}})}}}\\right)}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>as a function of \u03bb.<\/jats:p>","DOI":"10.1017\/s0963548319000154","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T08:50:09Z","timestamp":1564044609000},"page":"638-655","source":"Crossref","is-referenced-by-count":0,"title":["Expected Maximum Block Size in Critical Random Graphs"],"prefix":"10.1017","volume":"28","author":[{"given":"V.","family":"Rasendrahasina","sequence":"first","affiliation":[]},{"given":"A.","family":"Rasoanaivo","sequence":"additional","affiliation":[]},{"given":"V.","family":"Ravelomanana","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"S0963548319000154_ref26","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010407"},{"key":"S0963548319000154_ref25","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1988-0957061-X"},{"key":"S0963548319000154_ref23","doi-asserted-by":"crossref","unstructured":"[23] Panagiotou, K. (2009) Blocks in constrained random graphs with fixed average degree. In 21st International Conference on Formal Power Series and Algebraic Combinatorics.","DOI":"10.46298\/dmtcs.2710"},{"key":"S0963548319000154_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2014-12141-1"},{"key":"S0963548319000154_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548319000154_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040303"},{"key":"S0963548319000154_ref17","volume-title":"Combinatorial Enumeration","author":"Goulden","year":"1983"},{"key":"S0963548319000154_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20421"},{"key":"S0963548319000154_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195292053"},{"key":"S0963548319000154_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90087-3"},{"key":"S0963548319000154_ref8","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"S0963548319000154_ref5","doi-asserted-by":"crossref","first-page":"1993","DOI":"10.1214\/07-AAP514","article-title":"Finite size scaling for the core of large random hypergraphs","volume":"18","author":"Dembo","year":"2008","journal-title":"Ann. Appl. Probab"},{"key":"S0963548319000154_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548319000154_ref4","first-page":"48","article-title":"Random 2-XORSAT phase transition","volume":"59","author":"Daud\u00e9","year":"2009","journal-title":"Algorithmica"},{"key":"S0963548319000154_ref21","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198570431.001.0001","volume-title":"An Invitation to Discrete Mathematics","author":"Matou\u0161ek","year":"2008"},{"key":"S0963548319000154_ref24","first-page":"31","article-title":"Maximal biconnected subgraphs of random planar graphs","volume":"6","author":"Panagiotou","year":"2010","journal-title":"ACM Trans. Alg"},{"key":"S0963548319000154_ref27","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/jgt.3190040409","article-title":"The number of connected sparsely edged graphs III: Asymptotic results","volume":"4","author":"Wright","year":"1980","journal-title":"J. Graph Theory"},{"key":"S0963548319000154_ref1","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1002\/rsa.10021","article-title":"Random maps, coalescing saddles, singularity analysis, and Airy phenomena","volume":"19","author":"Banderier","year":"2001","journal-title":"Random Struct. Alg"},{"key":"S0963548319000154_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973037.1"},{"key":"S0963548319000154_ref18","volume-title":"Graphical Enumeration","author":"Harary","year":"1973"},{"key":"S0963548319000154_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.03.011"},{"key":"S0963548319000154_ref12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548319000154_ref13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","article-title":"Algorithmic theory of random graphs","volume":"10","author":"Frieze","year":"1997","journal-title":"Random Struct. Alg"},{"key":"S0963548319000154_ref15","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Statist"},{"key":"S0963548319000154_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20342"},{"key":"S0963548319000154_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46885-4_34"},{"key":"S0963548319000154_ref9","volume-title":"Mathematical Constants","author":"Finch","year":"2003"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T09:57:51Z","timestamp":1721555871000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000154\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["S0963548319000154"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000154","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}