Аннотация:
Доказана концентрация в интервале размера $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