Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-14T01:26:56.705Z 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: [email protected])
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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