- PII
- S2686954325030128-1
- DOI
- 10.31857/S2686954325030128
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 523 / Issue number 1
- Pages
- 71-74
- Abstract
- Consider — the set of all sizes (numbers of edges) of induced subgraphs of size in a given graph with vertices. For the binomial random graph , we proved that, for each and small enough, the set with high probability contains a large segment for all such that . We also found the asymptotic length of this segment.
- Keywords
- биноминальный случайный граф размеры индуцированных подграфов случайного графа
- Date of publication
- 21.04.2025
- Year of publication
- 2025
- Number of purchasers
- 0
- Views
- 12
References
- 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.
