Numero di cricca nei grafici casuali

Question

C'è una famiglia di grafici casuali $ G (n, p) $ con $ n $ nodi ( a causa di Gilbert ). Ogni possibile bordo viene inserito in modo indipendente in $ G (n, p) $ con probabilità p $ $. Sia $ X_k $ sia il numero di cricche di dimensioni $ k $ a $ G (n, p) $.

So che $ \ mathbb {E} (X_k) = \ tbinom {n} {k} \ cdot p ^ {\ tbinom {k} {2}} $, ma come faccio a dimostrarlo?

Come per dimostrare che $ \ mathbb {E} (X _ {\ log_2n}) \ GE1 $ a $ n \ to \ infty $? E come per dimostrare che $ \ mathbb {E} (X_ {c \ cdot \ log_2n}) \ to 0 $ a $ n \ to \ infty $ e un fisso, arbitraria costante $ c> 1 $?

Answer 1

Quindi, in pratica ci sono tre questioni coinvolte.

---

So che $ E (X_k) = \ tbinom {n} {k} \ cdot p ^ {\ tbinom {k} {2}} $, ma come faccio a dimostrarlo?

È possibile utilizzare la linearità di attesa e qualche intelligente ri-scrittura. Prima di tutto, si noti che $$ X_k = \ sum_. {T \ subseteq V, \, | T | = k} \ mathbb {1} [T \ text {} è cricca] $$ Ora, quando prende l'aspettativa di $ X_k $, si può semplicemente disegnare il fuori somma (a causa di linearità) e di ottenere $$ \ mathrm {E} (X_k) = \ sum_ {T \ subseteq V, \, | T | = k} \ mathrm {E} (\ mathbb {1} [testo T \ {è clique}]) = \ sum_ {T \ subseteq V, \, | T | = k} \ mathrm {} Pr [T \ text {} è cricca] $$ Estraendo la somma, abbiamo eliminato tutte le possibili dipendenze tra i sottoinsiemi dei nodi. Quindi, qual è la probabilità che $ T $ è una cricca? Beh, non importa quale $ T $ è composto da, tutte le probabilità bordo sono uguali. Pertanto, $ \ mathrm {} Pr [T \ text {} è cricca] = p ^ {k \ scegliere 2} $, dal momento che tutti i bordi di questo sottografo devono essere presenti. E poi, il termine interno della somma non dipende da $ T $ più, lasciandoci con $ \ mathrm {E} (X_k) = p ^ {k \ scegliere 2} \ sum_ {T \ subseteq V, \, | T |. = k} 1 = {\ n scegliere k} \ cdot p ^ {k \ scegliere 2} $

---

Come mostrare che per $ n \ rightarrow \ infty $: $ E (X _ {\ log_2n}) \ GE1 $

Non sono del tutto sicuro se questo è anche corretto. L'applicazione di un legato sul coefficiente binomiale, si ottiene

$$ E (X _ {\ log n}) = {n \ scegliere \ log n} \ cdot p ^ {\ log n \ scegliere 2} \ leq \ left (\ frac {NEP ^ \ frac {(\ log n)} {4}} {\ Log n} \ right) ^ {\ log n} = \ left (\ frac {ne \ cdot n ^ {(\ log p) / 4}} {\ log n} \ a destra) ^ {\ log n}. $$ (Si noti che ho circa superiore delimitata $ p ^ \ frac {-1 + \ log n} {2} $ di $ p ^ \ frac {\ log n} {4} $.) Tuttavia, ora si può scegliere $ p = 0.001 $, ed ottenere che $ \ log_2 0.001 \ circa -9,96 $, che rende l'intero go termine a $ 0 $ per grandi $ n $. Stai forse mancano alcune ipotesi su $ p $?