{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T05:47:11Z","timestamp":1746078431349},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5582,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:p>Let <jats:italic>H<\/jats:italic> be a graph on <jats:italic>h<\/jats:italic> vertices, and <jats:italic>G<\/jats:italic> be a graph on <jats:italic>n<\/jats:italic> vertices. An <jats:italic>H-factor<\/jats:italic> of <jats:italic>G<\/jats:italic> is a spanning subgraph of <jats:italic>G<\/jats:italic> consisting of <jats:italic>n\/h<\/jats:italic> vertex disjoint copies of <jats:italic>H<\/jats:italic>. The <jats:italic>fractional arboricity<\/jats:italic> of <jats:italic>H<\/jats:italic> is <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000559inline1\" \/>, where the maximum is taken over all subgraphs (<jats:italic>V<\/jats:italic>\u2032, E\u2032) of <jats:italic>H<\/jats:italic> with |<jats:italic>V\u2032<\/jats:italic>| &gt; 1. Let \u03b4(<jats:italic>H<\/jats:italic>) denote the minimum degree of a vertex of <jats:italic>H<\/jats:italic>. It is shown that if \u03b4(<jats:italic>H<\/jats:italic>) &lt; <jats:italic>a<\/jats:italic>(<jats:italic>H<\/jats:italic>), then n<jats:sup>\u22121\/<jats:italic>a<\/jats:italic>(<jats:italic>H<\/jats:italic><\/jats:sup>) is a sharp threshold function for the property that the random graph <jats:italic>G<\/jats:italic>(<jats:italic>n, p<\/jats:italic>) contains an <jats:italic>H<\/jats:italic>-factor. That is, there are two positive constants <jats:italic>c<\/jats:italic> and C so that for <jats:italic>p<\/jats:italic>(<jats:italic>n<\/jats:italic>) = <jats:italic>cn<\/jats:italic><jats:sup>\u22121\/<jats:italic>a<\/jats:italic>(<jats:italic>H<\/jats:italic><\/jats:sup>) almost surely <jats:italic>G<\/jats:italic>(<jats:italic>n, p<\/jats:italic>(<jats:italic>n<\/jats:italic>)) does not have an <jats:italic>H<\/jats:italic>-factor, whereas for <jats:italic>p<\/jats:italic>(<jats:italic>n<\/jats:italic>) = <jats:italic>Cn<\/jats:italic><jats:sup>\u22121\/<jats:italic>a<\/jats:italic>(<jats:italic>H<\/jats:italic><\/jats:sup>), almost surely <jats:italic>G<\/jats:italic>(<jats:italic>n, p<\/jats:italic>(<jats:italic>n<\/jats:italic>)) contains an <jats:italic>H<\/jats:italic>-factor (provided <jats:italic>h<\/jats:italic> divides <jats:italic>n<\/jats:italic>). A special case of this answers a problem of Erd\u0151s.<\/jats:p>","DOI":"10.1017\/s0963548300000559","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T07:19:08Z","timestamp":1221203948000},"page":"137-144","source":"Crossref","is-referenced-by-count":19,"title":["Threshold Functions for <i>H<\/i>-factors"],"prefix":"10.1017","volume":"2","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000559_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S0963548300000559_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"S0963548300000559_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"},{"key":"S0963548300000559_ref005","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"S0963548300000559_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90022-8"},{"key":"S0963548300000559_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"S0963548300000559_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271712"},{"key":"S0963548300000559_ref003","volume-title":"The Probabilistic Method","author":"Alon","year":"1991"},{"key":"S0963548300000559_ref012","first-page":"345","article-title":"Matching is as easy as matrix inversion","author":"Mulmuley","year":"1987","journal-title":"Proc. 19th ACM STOC"},{"key":"S0963548300000559_ref008","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010209"},{"key":"S0963548300000559_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90061-Z"},{"key":"S0963548300000559_ref010","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4226"},{"key":"S0963548300000559_ref013","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"S0963548300000559_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"S0963548300000559_ref011","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000559","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T18:49:17Z","timestamp":1557946157000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000559\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["S0963548300000559"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000559","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}