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

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

МАТЕМАТИКА

Максимальные индуцированные деревья в разреженных случайных графах

Х. К. Буитраго Оропеса

Московский физико-технический институт (национальный исследовательский университет), Долгопрудный, Россия

Аннотация: Мы доказали, что для любого $\varepsilon>0$ и $n^{-(e-2)/(3e-2)+\varepsilon}\le p = o(1)$, максимальный размер индуцированного дерева в биномиальном случайном графе $G(n,p)$ сконцентрирован в двух последовательных значениях с вероятностью, стремящейся к $1$, при $n\to\infty$.

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

УДК: 519.175.4

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

DOI: 10.31857/S2686954324020133


 Англоязычная версия: Doklady Mathematics, 2024, 109:2, 167–169

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


© МИАН, 2025