Количество клики в случайных графах

Существует семейство случайных графов с узлов ( из - за Гилберт ). Каждый возможный край независимо друг от друга вставляется в с вероятностью . Пусть быть числом клик размера в . $G(n, p)$ $n$ $G(n, p)$ $p$ $X_k$ $k$ $G(n, p)$

Я знаю, что , но как мне это доказать? $\mathbb{E}(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$

Как показать , что для ? А как показать , что для и фиксированной, произвольной постоянной ? $\mathbb{E}(X_{\log_2n})\ge1$ $n\to\infty$ $\mathbb{E}(X_{c\cdot\log_2n}) \to 0$ $n\to\infty$ $c>1$

graph-theory combinatorics probability-theory random-graphs user1374864
источник

Поэтому в основном есть три вопроса, участвующий.

Я знаю , что , но как это доказать? $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$

Вы используете линейность ожидания и некоторые умные переписывания. Прежде всего, обратите внимание, что Теперь, принимая ожидание , можно просто вывести сумму (из-за линейности) и получить Выводя сумму, мы устранили все возможные зависимости между подмножествами узлов. Следовательно, какова вероятность того, что является кликой? Ну, независимо от того, из чего состоит , все вероятности ребер равны. Следовательно,

{Икс}_{К} знак равно \underset{T \subseteq В, | T | знак равно К}{Σ} 1 [T клика],

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

X_{k}

$X_k$

Е ({Икс}_{К}) знак равно \underset{T \subseteq В, | T | знак равно К}{Σ} Е (1 [T клика]) знак равно \underset{T \subseteq В, | T | знак равно К}{Σ} п р [T клика]

$\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}$ , поскольку все ребра в этом подграфе должны присутствовать. И затем, внутренний член суммы больше не зависит от , оставляя нас с .

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}$

Как показать это для : $n\rightarrow\infty$ $E(X_{\log_2n})\ge1$

Я не совсем уверен, правильно ли это. Применяя оценку биномиального коэффициента, получим

Е ({Икс}_{журнал N}) знак равно (\binom{N}{журнал N}) \cdot п^{(\binom{журнал N}{2})} \leq {(\frac{N е п^{\frac{(журнал N)}{4}}}{журнал N})}^{журнал N} знак равно {(\frac{N е \cdot N^{(журнал п) / 4}}{журнал N})}^{журнал 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}.$ (Обратите внимание, что я примерно ограничил верхнюю границу помощью .) Однако теперь можно было выбрать и получить это , что делает весь член для больших . Возможно, вы упускаете некоторые предположения о ?

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
источник

Это правильно? . Разве это не должно быть но сейчас я не знаю, как продолжить

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}$

Е ({Икс}_{журнал N}) знак равно (\binom{N}{{журнал}_{2} N}) \cdot п^{(\binom{{журнал}_{2} N}{2})} \leq {(\frac{N е}{{журнал}_{2} N})}^{журнал N} \cdot п^{\frac{({журнал}_{2} (N) \cdot е)^{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

Я применил упомянутый связанный только на . Для , вы можете заметить , что . Теперь , так как , мы хотим , чтобы сделать его показатель меньше (убедить себя , почему). Для достаточно большого , мы получаем , что . Поэтому выше расчет должен быть правильным ...

(\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

Что с третьим вопросом?

Очередь

Он страдает той же проблемой, что и второй вопрос. Извините, я должен был это уточнить.

HdM

Количество клики в случайных графах

Ответы:

Я знаю , что , но как это доказать?Е( ХК) = ( пК) ⋅р( к2)Е(ИксК)знак равно(NК)⋅п(К2)E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}

Как показать это для :E ( X log 2 n ) ≥ 1n → ∞N→∞n\rightarrow\inftyЕ( Хжурнал2N) ≥ 1Е(Иксжурнал2⁡N)≥1E(X_{\log_2n})\ge1

Я знаю , что , но как это доказать? $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$

Как показать это для : $n\rightarrow\infty$ $E(X_{\log_2n})\ge1$