{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T01:28:22Z","timestamp":1767835702420,"version":"3.49.0"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,4,22]],"date-time":"2024-04-22T00:00:00Z","timestamp":1713744000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline2.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-process generates a graph at random by starting with an empty graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline3.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices, then adding edges one at a time uniformly at random among all pairs of vertices which have degrees at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline4.png\"\/><jats:tex-math>\n$d-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and are not mutually joined. We show that, in the evolution of a random graph with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline5.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> vertices under the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline6.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-process with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline7.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> fixed, with high probability, for each <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline8.png\"\/><jats:tex-math>\n$j \\in \\{0,1,\\dots,d-2\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the minimum degree jumps from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline9.png\"\/><jats:tex-math>\n$j$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline10.png\"\/><jats:tex-math>\n$j+1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> when the number of steps left is on the order of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline11.png\"\/><jats:tex-math>\n$\\ln (n)^{d-j-1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This answers a question of Ruci\u0144ski and Wormald. More specifically, we show that, when the last vertex of degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline12.png\"\/><jats:tex-math>\n$j$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> disappears, the number of steps left divided by <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline13.png\"\/><jats:tex-math>\n$\\ln (n)^{d-j-1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> converges in distribution to the exponential random variable of mean <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline14.png\"\/><jats:tex-math>\n$\\frac{j!}{2(d-1)!}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; furthermore, these <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000105_inline15.png\"\/><jats:tex-math>\n$d-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> distributions are independent.<\/jats:p>","DOI":"10.1017\/s0963548324000105","type":"journal-article","created":{"date-parts":[[2024,4,22]],"date-time":"2024-04-22T09:14:09Z","timestamp":1713777249000},"page":"564-582","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Behaviour of the minimum degree throughout the \n${\\textit{d}}$\n-process"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8283-0985","authenticated-orcid":false,"given":"Jakob","family":"Hofstad","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,4,22]]},"reference":[{"key":"S0963548324000105_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20401"},{"key":"S0963548324000105_ref7","volume-title":"Random Graphs","author":"Janson","year":"2011"},{"key":"S0963548324000105_ref9","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/1274"},{"key":"S0963548324000105_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034625259"},{"key":"S0963548324000105_ref8","unstructured":"[8] Molloy, M. , Surya, E. and Warnke, L. (2022). The degree-restricted random process is far from uniform, arXiv preprint arXiv: 2211.00835."},{"key":"S0963548324000105_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000183"},{"key":"S0963548324000105_ref3","first-page":"477","article-title":"A note on the random greedy triangle-packing algorithm","volume":"1","author":"Bohman","year":"2010","journal-title":"J. Comb."},{"key":"S0963548324000105_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.04.015"},{"key":"S0963548324000105_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20133"},{"key":"S0963548324000105_ref1","volume-title":"The Probabilistic Method","author":"Alon","year":"2016"},{"key":"S0963548324000105_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20973"},{"key":"S0963548324000105_ref14","first-page":"0943","article-title":"The differential equation method for random graph processes and greedy algorithms","volume":"73","author":"Wormald","year":"1999","journal-title":"Lect. Approx. Random. Algor."},{"key":"S0963548324000105_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.02.018"},{"key":"S0963548324000105_ref12","unstructured":"[12] Ruci\u0144ski, A. and Wormald, N. (2023). Sharper analysis of the random graph $ d$ -process via a balls-in-bins model, arXiv preprint arXiv: 2311.04743."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T22:46:13Z","timestamp":1728427573000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000105\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,22]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["S0963548324000105"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000105","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,22]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike licence (https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the same Creative Commons licence is included and the original work is properly cited. The written permission of Cambridge University Press must be obtained for commercial re-use.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}