2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Оценка вероятности связности случайного графа
Сообщение10.05.2019, 21:48 


26/05/17
41
Москва
Нижняя оценка вероятности связности случайного графа $G_{n,p}$.
(Это неориентированный граф без петель и кратных ребер, в который каждое ребро полного графа на $n$ вершинах включается независимо от других ребер с вероятностью $p$.)

Вероятность того, что граф не связен, оценивается при $p(n)=\frac{c\ln n}{n}$, $c>1$, в статье Райгородского А.М. (ТРУДЫ МФТИ, 2010, Том 2, \No 4) фактически так.
Перебирая возможные множества вершин $V$, которые изолированы в графе, имеем
$$
\Prob\{G_{n,p}\text{ не связен }\}=\Prob\left(
\bigcup_{1\le k\le n-1} \bigcup_{|V|=k} \{V \text{ изолировано от остальных вершин}\} \right),
$$
что не превосходит $ 
\sum_{1\le k\le n-1} \tbinom{n}{k} (1-p)^{k(n-k)}\le \sum_{1\le k\le n/2} 2\tbinom{n}{k} (1-p)^{k(n-k)}=s(n,p). 
$
Далее автор пишет: "Оставшаяся часть рассуждения состоит в доказательстве того, что слагаемые с $k > 1$ и $k < n$ пренебрежимо малы по сравнению с первым слагаемым. Соответствующую выкладку мы пропустим. Если же поверить в ее справедливость, то получится, что вся сумма доминируется первым и последним слагаемыми, а стало быть, и она стремится к нулю."

Как все-таки доказать, что $s(n,p)\to 0$ при $n\to\infty$? Верно ли вообще это?
Отношение $ b_n:=\tfrac{a_{n+1}}{a_n}, \quad a_n=\tbinom{n}{k} (1-\tfrac{c\ln n}{n})^{k(n-k)} $ ведет себя не монотонно...

 Профиль  
                  
 
 Re: Оценка вероятности связности случайного графа
Сообщение11.05.2019, 02:02 


10/03/16
4444
Aeroport

(Оффтоп)

Гораздо интереснее было бы получить распределение числа компонент связности при больших n

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: dgwuqtj, mihaild


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group