В. С. Карась, П. А. Огарок, А. М. Райгородский, “Асимптотика числа независимости случайного подграфа графа $G(n,r,<s)$”, Докл. РАН. Матем., информ., проц. упр., 2021, том 499,страницы 17

Эта публикация цитируется в 1 статье

МАТЕМАТИКА

Асимптотика числа независимости случайного подграфа графа $G(n,r,<s)$

В. С. Карась^a, П. А. Огарок^b, А. М. Райгородский^abcd

^a Московский государственный университет имени М. В. Ломоносова, Москва, Россия
^b Московский физико-технический институт (национальный исследовательский университет), Долгопрудный, Московская обл., Россия
^c Кавказский математический центр, Адыгейский государственный университет, Майкоп, Республика Адыгея
^d Бурятский государственный университет, Институт математики и информатики, Улан-Удэ, Россия

Аннотация: Рассматривается вопрос о вероятностной версии классической проблемы экстремальной комбинаторики. Представлены обобщения на случай непостоянных параметров и на случай различных вероятностей ребра для теоремы устойчивости, утверждающей, что число независимости случайного подграфа графа $G(n,r,<s)$ асимптотически не изменяется при независимом удалении ребер.

Ключевые слова: асимптотика, число независимости, случайный подграф, граф $G(n,r,<s)$.

УДК: 519.1

Статья представлена к публикации: В. В. Козлов
Поступило: 26.03.2020
После доработки: 15.05.2021
Принято к публикации: 16.05.2021

DOI: 10.31857/S268695432104007X