Probabilidad de que un azar gráfico de ser triángulo libre

Question

Deje $S$ ser el conjunto de todos los grafos con conjunto de vértices $\{1,2,\ldots,n\}$. Un azar gráfico de $G\in S$ probabilidad de $2^{-{n \choose 2}}$. Mostrar que un azar gráfico casi seguramente contiene un triángulo.

Mi intento: queremos demostrar que como $n$ va al infinito, la probabilidad de un triángulo de libre gráfico va a cero. Traté de encontrar una fórmula general para la probabilidad de un triángulo de libre gráfico con $n$ vértices, pero parece imposible. Yo sé que para cualquiera de los tres vértices, la probabilidad de no ser un triángulo es $\frac{7}{8}$, pero no puedo calcular la probabilidad de la unión de todos los tres vértices. ¿Hay alguna otra forma de abordar este problema?

Answer 1

En esta situación, que en gran medida puede sobrestimar la probabilidad de que ningún triángulo y todavía conseguir acercarse a cero. Dividir el conjunto de $n$ vértices en distintos conjuntos de tamaño $3$ (tal vez uno o dos vértices si $n$ no es divisible por $3$). Así que ya tienes al menos $(n-2)/3$ pares distintos conjuntos de tamaño $3$. ¿Cuál es la probabilidad de que ninguno de estos conjuntos de formas un triángulo? Así, cada uno de estos conjuntos no se forma un triángulo con una probabilidad de $7/8$ (como se dijo en la pregunta). Y, porque los tres elementos de los conjuntos de bajo consideración son distintos, estas probabilidades para diferentes $3$-elemento de los conjuntos, son independientes. Por lo que la probabilidad de que ninguno de estos $(n-2)/3$ (o más) conjuntos de formas un triángulo es $(7/8)^{(n-2)/3}$ (o menos). Esto se aproxima a cero como $n\to\infty$.

La probabilidad de que no existen triángulos en todos es, por supuesto, $\leq$ la probabilidad de que ninguno de nuestros particular $3$-elemento de los conjuntos de formas un triángulo, por lo que también se aproxima a cero.

Answer 2

Considere la posibilidad de un azar el gráfico de $3n$ vértices. Dividir los vértices en $n$ trillizos. La probabilidad de que un determinado triplete no es un triángulo es $\frac78$, por lo que la probabilidad de que no triplete es un triángulo es $\left(\frac78\right)^n$. La probabilidad de que el gráfico es el triángulo es así en la mayoría de las $\left(\frac78\right)^n$, lo que tiende a $0$ $n$ aumenta sin límite.

Answer 3

Déjenme comenzar esta respuesta con la siguiente: La sobreestimación de los triángulos es un mucho mejor argumento para su problema en particular, ya que la probabilidad de un borde que aparece es fijo para todos los $n$. Si permites $p=p(n)$, entonces usted tiene que ser más cuidadoso. La técnica que sigue es la técnica, pero se puede adaptar muy fácilmente a mostrar para cualquier $p\ne o(\frac{\ln n}{n})$ que una.una.s. $G$ tendrá un triángulo.

---

Primero observar que, dado que la probabilidad de que cualquier $G$ existe $2^{-\binom{n}{2}}$ es equivalente a considerar cada una de las $\binom{n}{2}$ bordes ser elegido de forma independiente a aparecer en $G$ con una probabilidad de $p=1/2$.

Si dejamos $X$ ser discreto no negativo variable aleatoria que cuenta el número de triángulos en $G$, entonces queremos mostrar que $P(X=0)\to 0$$n\to\infty$. Vamos a usar el segundo método para obtener nuestro resultado.

Por Chebychev de la desigualdad y el hecho de que $X$ es una variable aleatoria no negativa, entonces sabemos que $$ P(X=0)\le P(|X-E(X)|\ge E(X))\le \frac{Var(X)}{E(X)^2}=\frac{E(X^2)-E(X)^2}{E(X)^2}=\frac{E(X^2)}{E(X)^2}-1. $$

Así que si podemos mostrar que $\frac{E(X^2)}{E(X)^2}\to 1$$n\to\infty$, entonces hemos terminado.

Observar que $E(X)=\binom{n}{3}p^3\approx c_1n^3$, de modo que $E(X)^2\approx c_2n^6$. Supongamos que vamos a enumerar todas las $\binom{n}{3}$ posible triples y para $1\le i\le \binom{n}{3}$ nos vamos $$ T_i=\begin{cases}1, &\text{if the }i\text{th triple is a triangle}\\0, &\text{otherwise}\end{casos}. $$

A continuación,$X=\sum T_i$, de modo que $$ X^2=\left(\sum_{i=1}^{\binom{n}{3}} T_i\right)^2=\sum_{1\le i,j\le\binom{n}{3}} T_iT_j $$ y $$ E(X^2)=\sum_{1\le i,j\le\binom{n}{3}} P(T_iT_j=1). $$ El lado derecho se puede dividir por el número de vértices que la $i$th y $j$th triángulos pueden tener en común: cero, uno, dos o tres en común. Así $$ \begin{align*} E(X^2)&=\sum_{1\le i,j\le\binom{n}{3}} P(T_iT_j=1)\\ &=\sum_{zero} P(T_iT_j=1)+\sum_{one} P(T_iT_j=1)+\sum_{two} P(T_iT_j=1)+\sum_{three} P(T_iT_j=1)\\ &=\binom{n}{3}\binom{n-3}{3}\frac{1}{2^6}+n\binom{n-1}{4}\frac{1}{2^6}+\binom{n}{2}\binom{n-2}{2}\frac{1}{2^5}+\binom{n}{3}\frac{1}{2^3}\\ &\approx c_3n^6+c_4n^5+c_5n^4+c_6n^3. \end{align*} $$ Así $$ \frac{E(X^2)}{E(X)^2}\approx\frac{c_3n^6+c_4n^5+c_5n^4+c_6n^3}{c_2n^6}=\frac{c_3}{c_2}+\frac{c_4}{c_2n}+\frac{c_5}{c_2n^2}+\frac{c_6}{c_2n^3}. $$ La observación de que $c_2=c_3=\frac{1}{3^22^8}$ $n\to\infty$ hemos $$ \frac{E(X^2)}{E(X)^2}\approx\frac{c_3}{c_2}+\frac{c_4}{c_2n}+\frac{c_5}{c_2n^2}+\frac{c_6}{c_2n^3}\a 1 $$ y nuestra conclusión de la siguiente manera.