Отправить статью по E-mail 
О РАЗМЕРАХ k-ПОДГРАФОВ БИНОМИАЛЬНОГО СЛУЧАЙНОГО ГРАФА
- Авторы: Яровиков Ю.Н1
-
Учреждения:
- Московский физико-технический институт (национальный исследовательский университет)
- Выпуск: Том 523, № 1 (2025)
- Страницы: 71-74
- Раздел: МАТЕМАТИКА
- URL: https://ogarev-online.ru/2686-9543/article/view/305349
- DOI: https://doi.org/10.7868/S3034504925030128
- EDN: https://elibrary.ru/JSYCAQ
- ID: 305349
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Рассмотрим E(G, k) — множество количеств ребер индуцированных подграфов размера k данного графа G на n вершинах. Мы доказали для любого α > 0 и достаточно малых ε, что если (ln n)1+α < k < en, то для биноминального случайного графа G = G(n, p), множество E(G, k) с высокой вероятностью содержит большое подмножество, которое представляет собой непрерывный отрезок, а также нашли асимптотику длины этого отрезка.
Об авторах
Ю. Н Яровиков
Московский физико-технический институт (национальный исследовательский университет)
Email: yu-rovikov@yandex.ru
Долгопрудный, Московская область, Россия
Список литературы
- Noga A., Kostochka A.V. Induced subgraphs with distinct sizes // Random Structures & Algorithms. 2009. V. 34. № 1. P. 45–53.
- Erdos P. Some of my favorite problems in various branches of combinatorics // Matematiche (Catania). 1992. V. 47. P. 231–240.
- Erdos P. Some recent problems and results in graph theory // Discrete Math. 1997. V. 164. P. 81–85.
- Balogh J., Zhukovskii M. On the sizes of large subgraphs of the binomial random graph // Discrete Mathematics. 2022. V. 345. № 2. P. 112675.
- Janson S., Luczak T., Rucinski A. Random graphs. John Wiley & Sons. 2011.
- El Cheairi H., Gamarnik D. Densest subgraphs of a dense Erdos-Renyi graph. Asymptotics, landscape and universality // arXiv e-prints. 2022. C. arXiv: 2212.03925.
- Erdos P., Szemeredi A. On a Ramsey type theorem // Periodica Mathematica Hungarica. 1972. V. 2. № 1–4. P. 295–299.
- Kwan M., Sudakov B. Proof of a conjecture on induced subgraphs of Ramsey graphs // Transactions Amer. Math. Soc. 2019. V. 372. P. 5571–5594.
- Alon N., Spencer J.H. The probabilistic method. John Wiley & Sons. 2016.
Дополнительные файлы
Примечание
В печатной версии статья выходила под DOI: 10.31857/S2686954325030128