RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2020, том 56, выпуск 4, страницы 50–63 (Mi ppi2328)

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

Большие системы

Об устойчивости числа независимости некоторого дистанционного графа

П. А. Огарокa, А. М. Райгородскийbcdeaf

a Московский физико-технический институт (государственный университет), факультет инноваций и высоких технологий, кафедра дискретной математики
b Московский физико-технический институт (государственный университет), Физтех-школа прикладной математики и информатики
c Бурятский государственный университет, институт математики и информатики
d Кавказский математический центр Адыгейского государственного университета
e Московский государственный университет им. М.В. Ломоносова, механико-математический факультет, кафедра математической статистики и случайных процессов
f Лаборатория продвинутой комбинаторики и сетевых приложений

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

Ключевые слова: случайный граф, дистанционный граф, число независимости.

УДК: 621.391 : 519.176

Поступила в редакцию: 09.03.2020
После переработки: 29.10.2020
Принята к печати: 29.10.2020

DOI: 10.31857/S0555292320040051


 Англоязычная версия: Problems of Information Transmission, 2020, 56:4, 345–357

Реферативные базы данных:


© МИАН, 2024