{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T07:40:48Z","timestamp":1768549248180,"version":"3.49.0"},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We show that the twin-width of every <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000439_inline1.png\"\/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000439_inline2.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-regular graph is at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000439_inline3.png\"\/><jats:tex-math>\n$n^{\\frac{d-2}{2d-2}+o(1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for any fixed integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000439_inline4.png\"\/><jats:tex-math>\n$d \\geq 2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and that almost all <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000439_inline5.png\"\/><jats:tex-math>\n$d$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erd\u0151s\u2013Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim, and Oum.<\/jats:p>","DOI":"10.1017\/s0963548324000439","type":"journal-article","created":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T03:07:08Z","timestamp":1733886428000},"page":"401-420","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Twin-width of sparse random graphs"],"prefix":"10.1017","volume":"34","author":[{"given":"Kevin","family":"Hendrey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Norin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4555-8425","authenticated-orcid":false,"given":"J\u00e9r\u00e9mie","family":"Turcotte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"key":"S0963548324000439_ref5","article-title":"Twin-width II: small classes","volume":"2","author":"Bonnet","year":"2022","journal-title":"Comb. Theory"},{"key":"S0963548324000439_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/18.59935"},{"key":"S0963548324000439_ref8","first-page":"601","volume-title":"Combinatorial Theory and Its Applications","author":"Hajnal","year":"1970"},{"key":"S0963548324000439_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0025557200006690"},{"key":"S0963548324000439_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3486655"},{"key":"S0963548324000439_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548324000439_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1091"},{"key":"S0963548324000439_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275671"},{"key":"S0963548324000439_ref12","unstructured":"[12] Sylvester, J. Open Problems - 1st Twin-Width Workshop 2023, Problem 9. Private communication"},{"key":"S0963548324000439_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21247"},{"key":"S0963548324000439_ref2","unstructured":"[2] Ahn, J. , Chakraborti, D. , Hendrey, K. and Oum, S.-il. (2023) Twin-width of subdivisions of multigraphs. URL: http:\/\/arxiv.org\/abs\/2306.05334"},{"key":"S0963548324000439_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/21M1452834"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000439","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T05:00:45Z","timestamp":1745902845000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000439\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["S0963548324000439"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000439","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,11]]},"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"}}]}}