Probabilidad de que un azar grafo es planar

Question

He estado tratando de resolver el reto siguiente problema a partir de una combinatoria de clase pero estoy haciendo absolutamente nada.

Probar: Para suficientemente grande $n$, la probabilidad de un azar del gráfico de $G=(V,E)$ $n$ vértices es planar es menos de $2^{-0.49n^2}$.

He descartado el uso de Kuratowski la caracterización de planaridad para probar esto (ya sé que es difícil determinar si es o no un subgrafo $G' \subset G$ es topológico, $K_{3,3}$ o $K_5$. El otro caracterización soy consciente es de que si un grafo es planar, $\exists v \in V$ tal que $deg[v] \leq 5$. Por lo que la probabilidad de un azar del grafo es planar es equivalente a $1-\mathbb{P}$ donde $\mathbb{P} = $ la probabilidad de que un azar gráfica no tiene vértices de grado menor o igual a 5.

Sin embargo, no veo cómo proceder a partir de esta observación. Soluciones/sugerencias se agradece.

Answer 1

Un azar el gráfico de $n$ vértices es un gráfico que tiene cada una de las $n\choose2$ bordes de forma independiente con una probabilidad de $1/2$ cada uno. La probabilidad de que en la mayoría de las $3n-6$ bordes (que es una condición necesaria para la planaridad) es $$2^{-n(n-1)/2}\sum_{k=0}^{3n-6}{n(n-1)/2\choose k}$$ Existen métodos estándar para la estimación de la suma.