Нижняя оценка вероятности связности случайного графа
.
(Это неориентированный граф без петель и кратных ребер, в который каждое ребро полного графа на
вершинах включается независимо от других ребер с вероятностью
.)
Вероятность того, что граф не связен, оценивается при
,
, в статье Райгородского А.М. (ТРУДЫ МФТИ, 2010, Том 2, \No 4) фактически так.
Перебирая возможные множества вершин
, которые изолированы в графе, имеем
что не превосходит
Далее автор пишет: "Оставшаяся часть рассуждения состоит в доказательстве того, что слагаемые с
и
пренебрежимо малы по сравнению с первым слагаемым. Соответствующую выкладку мы пропустим. Если же поверить в ее справедливость, то получится, что вся сумма доминируется первым и последним слагаемыми, а стало быть, и она стремится к нулю."
Как все-таки доказать, что
при
? Верно ли вообще это?
Отношение
ведет себя не монотонно...