Número de camarilla en grafos aleatorios

Question

Hay una familia de grafos aleatorios $ G (n, p) $ con $ n $ nodos ( debido a Gilbert ). Cada borde posible se inserta de forma independiente en $ G (n, p) $ con probabilidad $ p $. Sea $ x_k $ es el número de grupos de tamaño $ k $ en $ G (n, p) $.

Sé que $ \ mathbb {E} (x_k) = \ tbinom {n} {k} \ cdot p ^ {\ tbinom {k} {2}} $, pero ¿cómo lo demuestre?

Como para demostrar que $ \ mathbb {E} (X _ {\ log_2n}) \ ge1 $ por $ n \ to \ infty $? Y la forma de demostrar que $ \ mathbb {E} (X_ {c \ cdot \ log_2n}) \ a 0 $ por $ n \ to \ infty $ y una fija, arbitraria constante c $> $ 1?

Answer 1

Así que, básicamente hay tres cuestiones planteadas.

---

Sé que $ E (x_k) = \ tbinom {n} {k} \ cdot p ^ {\ tbinom {k} {2}} $, pero ¿cómo lo demuestre?

Se utiliza la linealidad de la expectativa y algunas re-escritura inteligente. En primer lugar, cabe destacar que $$ x_k = \ sum_. {T \ subseteq V, \, | T | = k} \ mathbb {1} [T \ text {es clique}] $$ Ahora, al tomar la expectativa de $ x_k $, se puede dibujar simplemente la suma fuera (debido a la linealidad) y obtener $$ \ mathrm {E} (x_k) = \ sum_ {T \ subseteq V, \, | T | = k} \ mathrm {E} (\ mathbb {1} [texto T \ {es clique}]) = \ sum_ {T \ subseteq V, \, | T | = k} \ mathrm {Pr} [t \ text {es} camarilla] $$ Extrayendo la suma, hemos eliminado todas las posibles dependencias entre subconjuntos de nodos. Por lo tanto, ¿cuál es la probabilidad de que T $ $ es una pandilla? Bueno, no importa lo $ T $ consiste en, todas las probabilidades marginales son iguales. Por lo tanto, $ \ mathrm {Pr} [t \ text {es} camarilla] = p ^ {k \ elegir 2} $, ya que todos los bordes de este subgrafo deben estar presentes. Y entonces, el término interno de la suma no depende de $ T $ más, que nos deja con $ \ mathrm {E} (x_k) = p ^ {k \ elegir 2} \ sum_ {T \ subseteq V, \, | T |. = k} = {1 \ n elegir k} \ cdot p ^ {k \ choose 2} $

---

¿Cómo demostrar que para n $ \ rightarrow \ infty $: $ E (X _ {\ log_2n}) \ ge1 $

No estoy del todo seguro de si esto es aún correcta. La aplicación de una obligado en el coeficiente binomial, obtenemos

$$ E (X _ {\ log n}) = {n \ choose \ log n} \ cdot p ^ {\ log n \ elegir 2} \ leq \ left (\ frac {NEP ^ \ frac {(\ log n)} {4}} {\ log n} \ right) ^ {\ log n} = \ left (\ frac {ne \ cdot n ^ {(\ log p) / 4}} {\ log n} \ derecha) ^ {\ log n}. $$ (Nota que más o menos acotada superiormente $ p ^ \ frac {-1 + \ log n} {2} $ por $ ^ p \ frac {\ log n} {4} $). Sin embargo, ahora uno puede elegir $ p = 0.001 $, y conseguir que $ \ log_2 0,001 \ aprox $ -9,96, lo que hace que todo el go plazo a $ 0 $ para grandes $ $ n. ¿Está quizá faltan algunos supuestos sobre $ p $?