RUS  ENG
Полная версия
ЖУРНАЛЫ // Доклады Российской академии наук. Математика, информатика, процессы управления // Архив

Докл. РАН. Матем., информ., проц. упр., 2024, том 516, страницы 21–25 (Mi danma508)

МАТЕМАТИКА

Индуцированные леса и деревья в случайном графе Эрдёша–Реньи

М. Б. Ахмеджановаa, В. С. Кожевниковb

a Научно-технологический университет имени короля Абдаллы, Кауст, Саудовская Аравия
b Московский физико-технический институт (национальный исследовательский университет), Москва, Россия

Аннотация: Доказана концентрация в интервале размера $2+o(1/p)$ размера максимального индуцированного леса (ограниченной и неограниченной степени) в $G(n, p)$ при $C_\varepsilon/n<p<1-\varepsilon$ для произвольного заданного $\varepsilon>0$. Доказана двухточечная концентрация размера максимального индуцированного леса (а также дерева) ограниченной степени в биномиальном случайном графе Эрдёша–Реньи $G(n,p)$ при $p=\operatorname{const}$.

Ключевые слова: случайный граф, граф Эрдёша–Реньи, индуцированный подграф, дерево, лес.

УДК: 519.175.4

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

DOI: 10.31857/S2686954324020041


 Англоязычная версия: Doklady Mathematics, 2024, 516:2, 117–120

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


© МИАН, 2025