{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T03:12:59Z","timestamp":1716347579713},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2011,6,9]],"date-time":"2011-06-09T00:00:00Z","timestamp":1307577600000},"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>The classical Erd\u0151s\u2013P\u00f3sa theorem states that for each positive integer <jats:italic>k<\/jats:italic> there is an <jats:italic>f<\/jats:italic>(<jats:italic>k<\/jats:italic>) such that, in each graph <jats:italic>G<\/jats:italic> which does not have <jats:italic>k<\/jats:italic> + 1 disjoint cycles, there is a blocker of size at most <jats:italic>f<\/jats:italic>(<jats:italic>k<\/jats:italic>); that is, a set <jats:italic>B<\/jats:italic> of at most <jats:italic>f<\/jats:italic>(<jats:italic>k<\/jats:italic>) vertices such that <jats:italic>G<\/jats:italic>\u2212<jats:italic>B<\/jats:italic> has no cycles. We show that, amongst all such graphs on vertex set {1,.\u00a0.\u00a0.,<jats:italic>n<\/jats:italic>}, all but an exponentially small proportion have a blocker of size <jats:italic>k<\/jats:italic>. We also give further properties of a random graph sampled uniformly from this class, concerning uniqueness of the blocker, connectivity, chromatic number and clique number.<\/jats:p><jats:p>A key step in the proof of the main theorem is to show that there must be a blocker as in the Erd\u0151s\u2013P\u00f3sa theorem with the extra \u2018redundancy\u2019 property that <jats:italic>B<\/jats:italic>\u2013<jats:italic>v<\/jats:italic> is still a blocker for all but at most <jats:italic>k<\/jats:italic> vertices <jats:italic>v<\/jats:italic> \u2208 <jats:italic>B<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548311000186","type":"journal-article","created":{"date-parts":[[2011,6,9]],"date-time":"2011-06-09T09:01:05Z","timestamp":1307610065000},"page":"763-775","source":"Crossref","is-referenced-by-count":4,"title":["Random Graphs with Few Disjoint Cycles"],"prefix":"10.1017","volume":"20","author":[{"given":"VALENTAS","family":"KURAUSKAS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"COLIN","family":"McDIARMID","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,6,9]]},"reference":[{"key":"S0963548311000186_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"S0963548311000186_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20355"},{"key":"S0963548311000186_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33700-8_15"},{"key":"S0963548311000186_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.09.007"},{"key":"S0963548311000186_ref12","first-page":"73","article-title":"Some remarks on the theory of trees","volume":"4","author":"R\u00e9nyi","year":"1959","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"S0963548311000186_ref2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"S0963548311000186_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271272"},{"key":"S0963548311000186_ref5","doi-asserted-by":"crossref","unstructured":"[5] Kurauskas V. and McDiarmid C. (2011) Random graphs containing few disjoint excluded minors. Manuscript.","DOI":"10.1002\/rsa.20447"},{"key":"S0963548311000186_ref7","volume-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1993"},{"key":"S0963548311000186_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309009717"},{"key":"S0963548311000186_ref6","first-page":"289","article-title":"On graphs not containing independent circuits (Hungarian)","volume":"16","author":"Lov\u00e1sz","year":"1965","journal-title":"Mat. Lapok"},{"key":"S0963548311000186_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548311000186_ref1","first-page":"459","article-title":"Some results concerning the structure of graphs","volume":"8","author":"Dirac","year":"1965","journal-title":"Canad. Math. Bull."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T06:33:51Z","timestamp":1556346831000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000186\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,9]]},"references-count":13,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["S0963548311000186"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000186","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,9]]}}}