{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:57Z","timestamp":1747173537270,"version":"3.40.5"},"reference-count":32,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T00:00:00Z","timestamp":1714694400000},"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":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We find asymptotics of the maximum size of a chordal subgraph in a binomial random graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000154_inline1.png\"\/><jats:tex-math>\n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000154_inline2.png\"\/><jats:tex-math>\n$p=\\mathrm{const}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000154_inline3.png\"\/><jats:tex-math>\n$p=n^{-\\alpha +o(1)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548324000154","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T08:24:10Z","timestamp":1714724650000},"page":"611-623","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Maximum chordal subgraphs of random graphs"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2357-4982","authenticated-orcid":false,"given":"Michael","family":"Krivelevich","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8763-9533","authenticated-orcid":false,"given":"Maksim","family":"Zhukovskii","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"S0963548324000154_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831300045X"},{"key":"S0963548324000154_ref25","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12718"},{"key":"S0963548324000154_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548323000068"},{"key":"S0963548324000154_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113480"},{"key":"S0963548324000154_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20738"},{"key":"S0963548324000154_ref18","unstructured":"[18] Gishboliner, L. (2022) Talk at the workshop \u201cRecent advances in probabilistic and extremal combinatorics\u201d, Ascona."},{"key":"S0963548324000154_ref22","unstructured":"[22] Hoshen, I. and Samotij, W. (2023) Simonovits\u2019s theorem in random graphs. arXiv: 2308.13455."},{"key":"S0963548324000154_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548324000154_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-55121-2_17"},{"key":"S0963548324000154_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271712"},{"key":"S0963548324000154_ref15","unstructured":"[15] Erd\u0151s, P. and Laskar, R. (1985) A note on the size of a chordal subgraph. In Southeastern International Conference on Graphs, Combinatorics and Computing, Utilitas Mathematica Publishing Co., pp. 81\u201386."},{"key":"S0963548324000154_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20413"},{"key":"S0963548324000154_ref28","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","year":"2004","author":"Golumbic","key":"S0963548324000154_ref20"},{"volume-title":"Introduction to Graph Theory","year":"2001","author":"West","key":"S0963548324000154_ref32"},{"key":"S0963548324000154_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3"},{"key":"S0963548324000154_ref30","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2016.184.2.1"},{"key":"S0963548324000154_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548324000154_ref12","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1084"},{"key":"S0963548324000154_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90002-8"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1990","author":"Garey","key":"S0963548324000154_ref17"},{"key":"S0963548324000154_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"S0963548324000154_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"S0963548324000154_ref24","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008374125234"},{"key":"S0963548324000154_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20535"},{"key":"S0963548324000154_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90141-2"},{"key":"S0963548324000154_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20096"},{"key":"S0963548324000154_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/9781108592376.009"},{"key":"S0963548324000154_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"S0963548324000154_ref9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2016.184.2.2"},{"key":"S0963548324000154_ref31","doi-asserted-by":"publisher","DOI":"10.1561\/2400000006"},{"key":"S0963548324000154_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020206"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T22:46:10Z","timestamp":1728427570000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000154\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,3]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["S0963548324000154"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000154","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,5,3]]},"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"}}]}}