{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T00:19:12Z","timestamp":1596068352218},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"URL":"https:\/\/www.cambridge.org\/core\/terms","start":{"date-parts":[[2013,7,22]],"date-time":"2013-07-22T00:00:00Z","timestamp":1374451200000},"delay-in-days":0,"content-version":"unspecified"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,9]]},"abstract":"Let G<\/jats:italic> be a finite graph with minimum degree r<\/jats:italic>. Form a random subgraph Gp<\/jats:sub><\/jats:italic> of G<\/jats:italic> by taking each edge of G<\/jats:italic> into Gp<\/jats:sub><\/jats:italic> independently and with probability p<\/jats:italic>. We prove that for any constant \u03b5 > 0, if $p=\\frac{1+\\epsilon}{r}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then Gp<\/jats:sub><\/jats:italic> is non-planar with probability approaching 1 as 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-22T10:08:05Z","timestamp":1374487685000},"page":"722-732","source":"Crossref","is-referenced-by-count":6,"title":["On the Non-Planarity of a Random Subgraph"],"prefix":"10.1017","volume":"22","author":[{"given":"ALAN","family":"FRIEZE","sequence":"first","affiliation":[]},{"given":"MICHAEL","family":"KRIVELEVICH","sequence":"additional","affiliation":[]}],"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","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","doi-asserted-by":"crossref"},{"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","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","doi-asserted-by":"crossref"},{"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","unstructured":"Bollob\u00e1s B. (2001) Random Graphs, second edition, Cambridge University Press.","DOI":"10.1017\/CBO9780511814068","doi-asserted-by":"crossref"},{"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-23T20:04:10Z","timestamp":1556049850000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,22]]},"references-count":12,"journal-issue":{"published-print":{"date-parts":[[2013,9]]},"issue":"5"},"alternative-id":["S0963548313000308"],"URL":"http:\/\/dx.doi.org\/10.1017\/s0963548313000308","relation":{"cites":[]},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":["Theoretical Computer Science","Statistics and Probability","Computational Theory and Mathematics","Applied Mathematics"]}}