Числа независимости случайных подграфов графов Джонсона
Автор: Синельников-мурылев П.С.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 1 (65) т.17, 2025 года.
Бесплатный доступ
В работе рассматриваются обобщенные графы Джонсона G(n, r, s) и их случайные подграфы Gp(n, r, s). Основной темой исследования являются асимптотические оценки числа независимости (максимального независимого множества) в таких случайных подграфах. Сформулирована и доказана теорема об асимптотической оценке снизу числа независимости случайного графа Джонсона.
Граф джонсона, случайные подграфы, число независимости, асимптотические оценки, вероятностные методы в комбинаторике
Короткий адрес: https://sciup.org/142245197
IDR: 142245197 | УДК: 111.111
Independence numbers of random subgraphs of Johnson graphs
In this paper, we consider generalized Johnson graphs G(n, r, s) and their random subgraphs Gp(n, r, s). The main topic of the study is asymptotic estimates of the independence number (maximal independent set) in such random subgraphs. A theorem on asymptotic estimation from below of the independence number of a Johnson random graph is formulated and proved.
