Email this article The size of a maximum subgraph of the random graph with a given number of edges
- Authors: Derevyanko N.M.1, Zhukovskii M.E.1,2,3, Rassias M.4, Skorkin A.Y.5
-
Affiliations:
- Moscow Institute of Physics and Technology
- Caucasus Mathematical Center
- The Russian Presidential Academy of National Economy and Public Administration
- University of Zurich
- Adygea State University
- Issue: Vol 488, No 6 (2019)
- Pages: 587-589
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/17712
- DOI: https://doi.org/10.31857/S0869-56524886587-589
- ID: 17712
Cite item
Full Text
Abstract
We have proven that the maximum size k of an induced subgraph of the binomial random graph G(n, p) with a given number of edges e(k) (under certain conditions on this function), with asymptotical probability 1, has at most two values.
Keywords
About the authors
N. M. Derevyanko
Moscow Institute of Physics and Technology
Email: zhukmax@gmail.com
Russian Federation, 9, Institutskiy lane, Dolgoprudny, Moscow region, 141701
M. E. Zhukovskii
Moscow Institute of Physics and Technology; Caucasus Mathematical Center; The Russian Presidential Academy of National Economy and Public Administration
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, 9, Institutskiy lane, Dolgoprudny, Moscow region, 141701; 208, Pervomayskaya str., Maykop, Republic of Adygea, 385016; 82, Vernadskogo av., Moscow, 119571
M. Rassias
University of Zurich
Email: zhukmax@gmail.com
Switzerland, 71, Rämistrasse, Zürich, 8006
A. Y. Skorkin
Adygea State University
Email: zhukmax@gmail.com
Russian Federation, 188, Universitetskaya str., Maikop, 385000
References
- Bollobás B. Random Graphs. 2nd ed. Cambridge: Cambridge Univ. Press, 2001.
- Janson S., Luczak T., Ruciński A. Random Graphs. N.Y.: Wiley, 2000.
- Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // Успехи матем. наук. 2015. T. 70. 1. С. 35-88.
- Деревянко Н.М., Киселев С.Г. Числа независимости случайных подграфов некоторого дистанционного графа // Проблемы передачи информации. 2017. Т. 53. № 4. С. 307-318.
- Егорова А.Н., Жуковский М.Е. Опровержение закона нуля или единицы для экзистенциальных монадических свойств разреженного биномиального случайного графа // ДАН. 2019. Т. 484. № 5. С. 519-522.
- Ostrovsky L.B., Zhukovskii M.E. Monadic Second-Order Properties of Very Sparse Random Graphs // Ann. Pure and Applied Logic. 2017. V. 168. № 11. P. 2087-2101.
- Bollobás B., Erdős P. Cliques in Random Graphs // Math. Proc. Camb. Phil. Soc. 1976. V. 80. P. 419-427.
- Grimmett G.R., McDiarmid C.J.H. On colouring random graphs // Math. Proc. Camb. Phil. Soc. 1975. V. 77. № 2. P. 313-324.
- Matula D. The Employee Party Problem // Not. Amer. Math. Soc. 1972. V. 19. № 2. P. A-382.
- Matula D. The Largest Clique Size in a Random Graph. Tech. Rep. Dept. Comp. Sci., Southern Methodist University, Dallas, Texas; 1976.
- Krivelevich M., Sudakov B., Vu V.H., Wormald N.C. On the Probability of Independent Sets in Random Graphs // Random Structures & Algorithms. 2003. V. 22. № 1. P. 1-14.
- Райгородский А.М. Об устойчивости числа независимости случайного подграфа // ДАН. 2017. Т. 477. № 6. С. 649-651.
- Fountoulakis N., Kang R.J., McDiarmid C. Largest Sparse Subgraphs of Random Graphs // European J. Combinatorics. 2014. V. 35. P. 232-244.
- Bollobás B. The Distribution of the Maximum Degree of a Random Graph // Discrete Mathematics. 1980. V. 32. P. 201-203.
Supplementary files
