{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:55:35Z","timestamp":1787324135427,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I3747"],"award-info":[{"award-number":["I3747"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I3747"],"award-info":[{"award-number":["I3747"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_196965"],"award-info":[{"award-number":["200021_196965"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by Erd\u00f6s and Bollob\u00e1s and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C\/n\\le p \\le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2\\log_q(np)$, where $q= \\frac{1}{1-p}$.<\/jats:p>","DOI":"10.1137\/20m1330609","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T10:08:56Z","timestamp":1613988536000},"page":"267-280","source":"Crossref","is-referenced-by-count":12,"title":["Large Induced Matchings in Random Graphs"],"prefix":"10.1137","volume":"35","author":[{"given":"Oliver","family":"Cooley","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nemanja","family":"Dragani\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihyun","family":"Kang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"atypb1","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , John Wiley & Sons, New York, 2004."},{"key":"atypb2","first-page":"419","author":"Bollob\u00e1s B.","year":"1976","journal-title":"Cambridge"},{"key":"atypb3","first-page":"47","volume":"24","author":"Clark L.","year":"2001","journal-title":"Australas. J. Combin."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788097"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<93::AID-RSA6>3.0.CO;2-6"},{"key":"atypb6","unstructured":"N. Dragani\u0107,\n                      Large Induced Trees in Dense Random Graphs\n                      , preprint, arXiv:2004.02800, 2020."},{"key":"atypb7","first-page":"168","author":"Dutta K.","year":"2018","journal-title":"Philadelphia"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90247-9"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90149-C"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579303"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90039-6"},{"key":"atypb12","unstructured":"S. Janson, T. \u0141uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , Vol. 45, John Wiley & Sons, New York, 2011."},{"key":"atypb13","first-page":"7","volume":"28","author":"Ku\u010dera L.","year":"1987","journal-title":"Comment. Math. Univ. Carolin."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90230-Q"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90215-4"},{"key":"atypb16","unstructured":"D. W. Matula,\n                      The Largest Clique Size in a Random Graph\n                      , Technical report CS 7608, Southern Methodist University, Dallas, TX, 1976."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90021-1"},{"key":"atypb18","first-page":"275","author":"Ruci\u0144ski A.","year":"1987","journal-title":"Ansterdam"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90021-O"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1330609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:12Z","timestamp":1787321952000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1330609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1330609"],"URL":"https:\/\/doi.org\/10.1137\/20m1330609","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}