On the non-planarity of a random subgraph

2012/05/29 by Frieze, Alan, Krivelevich, Michael
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1205.6240

Abstract

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

Related

• Uniform Random Planar Graphs with Degree Constraints
• On the probability of planarity of a random graph near the critical point
• Random planar maps and graphs with minimum degree two and three
• Planarity and genus of sparse random bipartite graphs
• The Effect of Induced Subgraphs on Quasi-Randomness