{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T17:10:40Z","timestamp":1703092240180},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T00:00:00Z","timestamp":1374451200000},"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":[[2013,9]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> be a finite graph with minimum degree <jats:italic>r<\/jats:italic>. Form a random subgraph <jats:italic>G<jats:sub>p<\/jats:sub><\/jats:italic> of <jats:italic>G<\/jats:italic> by taking each edge of <jats:italic>G<\/jats:italic> into <jats:italic>G<jats:sub>p<\/jats:sub><\/jats:italic> independently and with probability <jats:italic>p<\/jats:italic>. We prove that for any constant \u03b5 &gt; 0, if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000308_inline1\" \/><jats:tex-math>$p=\\frac{1+\\epsilon}{r}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then <jats:italic>G<jats:sub>p<\/jats:sub><\/jats:italic> is non-planar with probability approaching 1 as <jats:italic>r<\/jats:italic> grows. This generalizes classical results on planarity of binomial random graphs.<\/jats:p>","DOI":"10.1017\/s0963548313000308","type":"journal-article","created":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T06:08:05Z","timestamp":1374473285000},"page":"722-732","source":"Crossref","is-referenced-by-count":7,"title":["On the Non-Planarity of a Random Subgraph"],"prefix":"10.1017","volume":"22","author":[{"given":"ALAN","family":"FRIEZE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,7,22]]},"reference":[{"key":"S0963548313000308_ref2","unstructured":"Erd\u014fs P. and R\u00e9nyi A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17\u201361."},{"key":"S0963548313000308_ref11","doi-asserted-by":"crossref","unstructured":"Mader W. (2001) Subdivisions of a graph of maximal degree n+1 in graphs of average degree n + \u03b5 and large girth. Combinatorica 21 251\u2013265.","DOI":"10.1007\/s004930100023"},{"key":"S0963548313000308_ref4","unstructured":"Fountoulakis N. , K\u00fchn D. and Osthus D. (2009) Minors in random regular graphs. Random Struct. Alg. 35 444\u2013463."},{"key":"S0963548313000308_ref9","doi-asserted-by":"crossref","unstructured":"uczak T. and Wierman J. C. (1989) The chromatic number of random graphs at the double-jump threshold. Combinatorica 9 39\u201349.","DOI":"10.1007\/BF02122682"},{"key":"S0963548313000308_ref8","unstructured":"K\u00fchn D. and Osthus D. (2003) Minors in graphs of large girth. Random Struct. Alg. 22 213\u2013225."},{"key":"S0963548313000308_ref12","unstructured":"Noy M. , Ravelomanana V. and Ru\u00e9 J. On the probability of planarity of a random graph near the critical point, Proc. Amer. Math. Soc., to appear."},{"key":"S0963548313000308_ref7","unstructured":"Krivelevich M. , Lee C. and Sudakov B. Long paths and cycles in random subgraphs of graphs with large minimum degree. Random Struct. Alg., to appear."},{"key":"S0963548313000308_ref6","unstructured":"Krivelevich M. and Sudakov B. The phase transition in random graphs: A simple proof. Random Struct. Alg., to appear."},{"key":"S0963548313000308_ref1","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s B. (2001) Random Graphs, second edition, Cambridge University Press.","DOI":"10.1017\/CBO9780511814068"},{"key":"S0963548313000308_ref5","unstructured":"Krivelevich M. and Sudakov B. (2009) Minors in expanding graphs. Geom. Funct. Analysis 19 294\u2013331."},{"key":"S0963548313000308_ref3","unstructured":"Fountoulakis N. , K\u00fchn D. and Osthus D. (2008) The order of the largest complete minor in a random graph. Random Struct. Alg. 33 127\u2013141."},{"key":"S0963548313000308_ref10","unstructured":"uczak T. , Pittel B. and Wierman J. C. (1994) The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 721\u2013748."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T16:04:10Z","timestamp":1556035450000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000308\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,22]]},"references-count":12,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S0963548313000308"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000308","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,22]]}}}