Email this article 
ON THE SIZES OF k-SUBGRAPHS OF THE BINOMIAL RANDOM GRAPH
- Authors: Yarovikov Y.N1
-
Affiliations:
- Moscow Institute of Physics and Technology (National Research University)
- Issue: Vol 523, No 1 (2025)
- Pages: 71-74
- Section: MATHEMATICS
- URL: https://journals.rcsi.science/2686-9543/article/view/305349
- DOI: https://doi.org/10.31857/S2686954325030128
- EDN: https://elibrary.ru/JSYCAQ
- ID: 305349
Cite item
Open Access
Access granted
Subscription Access
Abstract
Consider E(G, k) — the set of all sizes (numbers of edges) of induced subgraphs of size k in a given graph G with n vertices. For the binomial random graph G = G(n, p), we proved that, for each α > 0 and ε small enough, the set E(G, k) with high probability contains a large segment for all k such that (ln n)1+α < k < εn. We also found the asymptotic length of this segment.
About the authors
Y. N Yarovikov
Moscow Institute of Physics and Technology (National Research University)
Email: yu-rovikov@yandex.ru
Dolgoprudny, Moscow Region, Russia
References
- 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.
Supplementary files
