{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T05:26:27Z","timestamp":1745472387361},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T00:00:00Z","timestamp":1308528000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>Let \u0394 \u2265 3 be an integer. Given a fixed <jats:italic><jats:bold>z<\/jats:bold><\/jats:italic> \u2208 <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000265_char1\" \/><\/jats:private-char><jats:sub>+<\/jats:sub><jats:sup>\u0394<\/jats:sup> such that <jats:italic>z<\/jats:italic><jats:sub>\u0394<\/jats:sub> &gt; 0, we consider a graph <jats:italic>G<\/jats:italic><jats:sub><jats:bold>z<\/jats:bold><\/jats:sub> drawn uniformly at random from the collection of graphs with <jats:italic>z<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic><\/jats:sub><jats:italic>n<\/jats:italic> vertices of degree <jats:italic>i<\/jats:italic> for <jats:italic>i<\/jats:italic> = 1,.\u00a0.\u00a0.,\u0394. We study the performance of the Karp\u2013Sipser algorithm when applied to <jats:italic>G<\/jats:italic><jats:sub><jats:bold>z<\/jats:bold><\/jats:sub>. If there is an index \u03b4 &gt; 1 such that <jats:italic>z<\/jats:italic><jats:sub>1<\/jats:sub> = .\u00a0.\u00a0. = <jats:italic>z<\/jats:italic><jats:sub>\u03b4\u22121<\/jats:sub> = 0 and \u03b4<jats:italic>z<\/jats:italic><jats:sub>\u03b4<\/jats:sub>,.\u00a0.\u00a0.,\u0394<jats:italic>z<\/jats:italic><jats:sub>\u0394<\/jats:sub> is a log-concave sequence of positive reals, then with high probability the Karp\u2013Sipser algorithm succeeds in finding a matching with <jats:italic>n<\/jats:italic> \u2225 <jats:bold>z<\/jats:bold> \u2225 <jats:sub>1<\/jats:sub>\/2 \u2212 <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>1\u2212\u03b5<\/jats:sup>) edges in <jats:italic>G<\/jats:italic><jats:sub><jats:bold>z<\/jats:bold><\/jats:sub>, where \u03b5 = \u03b5 (\u0394, <jats:bold>z<\/jats:bold>) is a constant.<\/jats:p>","DOI":"10.1017\/s0963548311000265","type":"journal-article","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T08:29:56Z","timestamp":1308558596000},"page":"721-741","source":"Crossref","is-referenced-by-count":14,"title":["Karp\u2013Sipser on Random Graphs with a Fixed Degree Sequence"],"prefix":"10.1017","volume":"20","author":[{"given":"TOM","family":"BOHMAN","sequence":"first","affiliation":[]},{"given":"ALAN","family":"FRIEZE","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,6,20]]},"reference":[{"key":"S0963548311000265_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20044"},{"key":"S0963548311000265_ref13","doi-asserted-by":"crossref","unstructured":"[13] Karp R. and Sipser M. (1981) Maximum matchings in sparse random graphs. In Proc. 22nd IEEE Symposium on the Foundations of Computing, pp. 364\u2013375.","DOI":"10.1109\/SFCS.1981.21"},{"key":"S0963548311000265_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662157.006"},{"key":"S0963548311000265_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548311000265_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"S0963548311000265_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00024-8"},{"key":"S0963548311000265_ref6","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"S0963548311000265_ref14","doi-asserted-by":"crossref","unstructured":"[14] Micali S. and Vazirani V. (1980) An O|V|1\/2|E|) algorithm for finding maximum matchings in general graphs. In Proc. 21st IEEE Symposium on the Foundations of Computing.","DOI":"10.1109\/SFCS.1980.12"},{"key":"S0963548311000265_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548311000265_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90172-7"},{"key":"S0963548311000265_ref10","first-page":"95","volume-title":"Trends in Mathematics","author":"Frieze","year":"2004"},{"key":"S0963548311000265_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#"},{"key":"S0963548311000265_ref17","unstructured":"[17] Wormald N. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms ( Karonski M. and Promel H. J. , eds), pp. 73\u2013155."},{"key":"S0963548311000265_ref16","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007693"},{"key":"S0963548311000265_ref4","first-page":"23","article-title":"On matchings and Hamiltonian cycles in random graphs.","volume":"28","author":"Bollob\u00e1s","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"S0963548311000265_ref5","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0937490100"},{"key":"S0963548311000265_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90077-8"},{"key":"S0963548311000265_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T06:33:23Z","timestamp":1556346803000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000265\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,20]]},"references-count":18,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["S0963548311000265"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000265","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,20]]}}}