Nombre de cliques dans les graphiques aléatoires

Donc, fondamentalement, il y a trois questions en jeu.

Je sais que $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$ , mais comment le prouver?

Vous utilisez la linéarité de l'attente et une réécriture intelligente. Tout d'abord, notez que Maintenant, en prenant l'espérance de , on peut simplement extraire la somme (en raison de la linéarité) et obtenir En extrayant la somme, nous avons éliminé toutes les dépendances possibles entre les sous-ensembles de nœuds. Quelle est donc la probabilité que soit une clique? Eh bien, quelle que soit la composition de , toutes les probabilités de front sont égales. Par conséquent,

X_{k} = \sum_{T \subseteq V, | T | = k} 1 [T is clique] .

$X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$

X_{k}

$X_k$

E (X_{k}) = \sum_{T \subseteq V, | T | = k} E (1 [T is clique]) = \sum_{T \subseteq V, | T | = k} P r [T is clique]

$\mathrm{E}(X_k) = \sum_{T \subseteq V, \, |T|=k} \mathrm{E}(\mathbb{1}[T \text{ is clique}]) = \sum_{T \subseteq V, \, |T|=k} \mathrm{Pr}[T \text{ is clique}]$

T

$T$

T

$T$

P r [T is clique] = p^{(\binom{k}{2})}

$\mathrm{Pr}[T \text{ is clique}] = p^{k \choose 2}$ , car toutes les arêtes de ce sous-graphique doivent être présentes. Et puis, le terme interne de la somme ne dépend plus de , nous laissant avec .

T

$T$

E (X_{k}) = p^{(\binom{k}{2})} \sum_{T \subseteq V, | T | = k} 1 = (\binom{n}{k}) \cdot p^{(\binom{k}{2})}

$\mathrm{E}(X_k) = p^{k \choose 2} \sum_{T \subseteq V, \, |T|=k} 1 = {n \choose k} \cdot p^{k \choose 2}$

Comment montrer que pour : $n\rightarrow\infty$ $E(X_{\log_2n})\ge1$

Je ne suis pas tout à fait sûr que ce soit même correct. En appliquant une borne sur le coefficient binomial, on obtient

E (X_{\log n}) = (\binom{n}{\log n}) \cdot p^{(\binom{\log n}{2})} \leq {(\frac{n e p^{\frac{(\log n)}{4}}}{\log n})}^{\log n} = {(\frac{n e \cdot n^{(\log p) / 4}}{\log n})}^{\log n} .

$E(X_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n} = \left(\frac{ne \cdot n^{(\log p) / 4}}{\log n}\right)^{\log n}.$ (Notez que j'ai à peu près la limite supérieure par .) Cependant, maintenant on pourrait choisir , et obtenir cela , ce qui fait que le terme entier passe à pour les grands . Vous manquez peut-être quelques hypothèses sur ?

p^{\frac{- 1 + \log n}{2}}

$p^\frac{-1 + \log n}{2}$

p^{\frac{\log n}{4}}

$p^\frac{\log n}{4}$

p = 0.001

$p = 0.001$

\log_{2} 0.001 \approx - 9.96

$\log_2 0.001 \approx -9.96$

0

$0$

n

$n$

p

$p$

HdM
la source

Est-ce correct? . Ne doit-il pas être mais maintenant je ne sais pas comment continuer

E (X_{\log n}) = (\binom{n}{\log n}) \cdot p^{(\binom{\log n}{2})} \leq {(\frac{n e p^{\frac{(\log n)}{4}}}{\log n})}^{\log n}

$E(X_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n}$

E (X_{\log n}) = (\binom{n}{\log_{2} n}) \cdot p^{(\binom{\log_{2} n}{2})} \leq {(\frac{n e}{\log_{2} n})}^{\log n} \cdot p^{\frac{(\log_{2} (n) \cdot e)^{2}}{4}}

$E(X_{\log n}) = {n \choose \log_2 n} \cdot p^{\log_2 n \choose 2} \leq \left(\frac{n e}{\log_2 n}\right)^{\log n}\cdot p^\frac{(\log_2 (n)\cdot e)^2}{4}$

user1374864

J'ai appliqué ladite limite uniquement sur . Pour , vous pouvez observer que . Maintenant, depuis , nous voulons rendre son exposant plus petit (vous convaincre pourquoi). Pour un assez grand , nous avons cela . Par conséquent, le calcul ci-dessus devrait être correct ...

(\binom{n}{\log n})

${n \choose \log n}$

p

$p$

(\binom{\log n}{2}) = (\log n) (\log n - 1) / 2

${\log n \choose 2} = (\log n) (\log n -1)/2$

p \leq 1

$p \leq 1$

n

$n$

(\log n) (\log n - 1) / 2 > (\log n)^{2} / 4

$(\log n) (\log n -1)/2 > (\log n)^2 / 4$

HdM

Quelle est la troisième question?

File d'attente

Elle souffre du même problème que la deuxième question. Désolé, j'aurais dû clarifier cela.

HdM

Nombre de cliques dans les graphiques aléatoires

Réponses:

Je sais que E( Xk) = ( nk)⋅p(k2)E(Xk)=(nk)⋅p(k2)E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}} , mais comment le prouver?

Comment montrer que pour :E ( X log 2 n ) ≥ 1n→∞n→∞n\rightarrow\inftyE(Xlog2n)≥1E(Xlog2⁡n)≥1E(X_{\log_2n})\ge1

Je sais que $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$ , mais comment le prouver?

Comment montrer que pour : $n\rightarrow\infty$ $E(X_{\log_2n})\ge1$