{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T05:46:49Z","timestamp":1775800009386,"version":"3.50.1"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"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,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study several basic problems about colouring the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline1.png\"\/>\n                        <jats:tex-math>$p$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -random subgraph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline2.png\"\/>\n                        <jats:tex-math>$G_p$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of an arbitrary graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline3.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , focusing primarily on the chromatic number and colouring number of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline4.png\"\/>\n                        <jats:tex-math>$G_p$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . In particular, we show that there exist infinitely many\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline5.png\"\/>\n                        <jats:tex-math>$k$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -regular graphs\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline6.png\"\/>\n                        <jats:tex-math>$G$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    for which the colouring number (i.e., degeneracy) of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline7.png\"\/>\n                        <jats:tex-math>$G_{1\/2}$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is at most\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline8.png\"\/>\n                        <jats:tex-math>$k\/3 + o(k)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with high probability, thus disproving the natural prediction that such random graphs must have colouring number at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000069_inline9.png\"\/>\n                        <jats:tex-math>$k\/2 - o(k)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1017\/s0963548325000069","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T04:24:59Z","timestamp":1745814299000},"page":"585-595","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Colouring random subgraphs"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4559-8336","authenticated-orcid":false,"given":"Boris","family":"Bukh","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2357-4982","authenticated-orcid":false,"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhargav","family":"Narayanan","sequence":"additional","affiliation":[{"name":"Rutgers University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"key":"S0963548325000069_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP822"},{"key":"S0963548325000069_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01285816"},{"key":"S0963548325000069_ref3","volume-title":"Wiley Series in Discrete Mathematics and Optimization","author":"Alon","year":"2016"},{"key":"S0963548325000069_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20158"},{"key":"S0963548325000069_ref11","first-page":"27","volume-title":"Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)","author":"Erd\u0151s","year":"1969"},{"key":"S0963548325000069_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90067-9"},{"key":"S0963548325000069_ref17","unstructured":"[17] Shinkar, I. (2016) On coloring random subgraphs of a fixed graph, arXiv: 1612.04319."},{"key":"S0963548325000069_ref9","doi-asserted-by":"publisher","DOI":"10.1088\/0022-3719\/12\/1\/008"},{"key":"S0963548325000069_ref8","volume-title":"Graduate Texts in Mathematics","volume":"184","author":"Bollob\u00e1s","year":"1998"},{"key":"S0963548325000069_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22571"},{"key":"S0963548325000069_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020444"},{"key":"S0963548325000069_ref12","first-page":"97","volume-title":"Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969)","author":"Erd\u0151s","year":"1971"},{"key":"S0963548325000069_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009825"},{"key":"S0963548325000069_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122551"},{"key":"S0963548325000069_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.38"},{"key":"S0963548325000069_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"S0963548325000069_ref14","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0963548325000069_ref19","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.082090499"},{"key":"S0963548325000069_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199708)25:4<295::AID-JGT7>3.0.CO;2-F"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:48:48Z","timestamp":1775796528000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000069\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S0963548325000069"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000069","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}