Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-06T19:50:36.016Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Non-Planarity of a Random Subgraph

Published online by Cambridge University Press:  22 July 2013

ALAN FRIEZE  and
MICHAEL KRIVELEVICH
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, USA (e-mail: alan@random.math.cmu.edu)
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: krivelev@post.tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let G be a finite graph with minimum degree r. Form a random subgraph Gp of G by taking each edge of G into Gp independently and with probability p. We prove that for any constant ε > 0, if $p=\frac{1+\epsilon}{r}$, then Gp is non-planar with probability approaching 1 as r grows. This generalizes classical results on planarity of binomial random graphs.

Keywords

Primary 05C80Secondary 05C10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 5 , September 2013 , pp. 722 - 732
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Bollobás, B. (2001) Random Graphs, second edition, Cambridge University Press.Google Scholar
[2]Erdŏs, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17–61.Google Scholar
[3]Fountoulakis, N., Kühn, D. and Osthus, D. (2008) The order of the largest complete minor in a random graph. Random Struct. Alg. 33 127–141.Google Scholar
[4]Fountoulakis, N., Kühn, D. and Osthus, D. (2009) Minors in random regular graphs. Random Struct. Alg. 35 444–463.Google Scholar
[5]Krivelevich, M. and Sudakov, B. (2009) Minors in expanding graphs. Geom. Funct. Analysis 19 294–331.Google Scholar
[6]Krivelevich, M. and Sudakov, B. The phase transition in random graphs: A simple proof. Random Struct. Alg., to appear.Google Scholar
[7]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.Google Scholar
[8]Kühn, D. and Osthus, D. (2003) Minors in graphs of large girth. Random Struct. Alg. 22 213–225.Google Scholar
[9]uczak, T. and Wierman, J. C. (1989) The chromatic number of random graphs at the double-jump threshold. Combinatorica 9 39–49.Google Scholar
[10]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–748.Google Scholar
[11]Mader, W. (2001) Subdivisions of a graph of maximal degree n+1 in graphs of average degree n + ε and large girth. Combinatorica 21 251–265.CrossRefGoogle Scholar
[12]Noy, M., Ravelomanana, V. and Rué, J. On the probability of planarity of a random graph near the critical point, Proc. Amer. Math. Soc., to appear.Google Scholar