- Код статьи
- S2686954325030128-1
- DOI
- 10.31857/S2686954325030128
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 523 / Номер выпуска 1
- Страницы
- 71-74
- Аннотация
- Рассмотрим — множество количеств ребер индуцированных подграфов размера данного графа на вершинах. Мы доказали для любого и достаточно малых , что если , то для биноминального случайного графа , множество с высокой вероятностью содержит большое подмножество, которое представляет собой непрерывный отрезок, а также нашли асимптотику длины этого отрезка.
- Ключевые слова
- биноминальный случайный граф размеры индуцированных подграфов случайного графа
- Дата публикации
- 21.04.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 11
Библиография
- 1. Noga A., Kostochka A.V. Induced subgraphs with distinct sizes // Random Structures & Algorithms. 2009. V. 34. № 1. P. 45–53.
- 2. Erdos P. Some of my favorite problems in various branches of combinatorics // Matematiche (Catania). 1992. V. 47. P. 231–240.
- 3. Erdos P. Some recent problems and results in graph theory // Discrete Math. 1997. V. 164. P. 81–85.
- 4. Balogh J., Zhukovskii M. On the sizes of large subgraphs of the binomial random graph // Discrete Mathematics. 2022. V. 345. № 2. P. 112675.
- 5. Janson S., Luczak T., Rucinski A. Random graphs. John Wiley & Sons. 2011.
- 6. 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.
- 7. Erdos P., Szemeredi A. On a Ramsey type theorem // Periodica Mathematica Hungarica. 1972. V. 2. № 1–4. P. 295–299.
- 8. Kwan M., Sudakov B. Proof of a conjecture on induced subgraphs of Ramsey graphs // Transactions Amer. Math. Soc. 2019. V. 372. P. 5571–5594.
- 9. Alon N., Spencer J.H. The probabilistic method. John Wiley & Sons. 2016.
