|
МАТЕМАТИКА
Индуцированные леса и деревья в случайном графе Эрдёша–Реньи
М. Б. Ахмеджанова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}$.
Ключевые слова:
случайный граф, граф Эрдёша–Реньи, индуцированный подграф, дерево, лес.
Образец цитирования:
М. Б. Ахмеджанова, В. С. Кожевников, “Индуцированные леса и деревья в случайном графе Эрдёша–Реньи”, Докл. РАН. Матем., информ., проц. упр., 516 (2024), 21–25; Dokl. Math., 516:2 (2024), 117–120
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/danma508 https://www.mathnet.ru/rus/danma/v516/p21
|
|