The size of a maximum subgraph of the random graph with a given number of edges

Cover Page

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.


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

  1. Bollobás B. Random Graphs. 2nd ed. Cambridge: Cambridge Univ. Press, 2001.
  2. Janson S., Luczak T., Ruciński A. Random Graphs. N.Y.: Wiley, 2000.
  3. Жуковский М.Е., Райгородский А.М. Случайные графы: модели и предельные характеристики // Успехи матем. наук. 2015. T. 70. 1. С. 35-88.
  4. Деревянко Н.М., Киселев С.Г. Числа независимости случайных подграфов некоторого дистанционного графа // Проблемы передачи информации. 2017. Т. 53. № 4. С. 307-318.
  5. Егорова А.Н., Жуковский М.Е. Опровержение закона нуля или единицы для экзистенциальных монадических свойств разреженного биномиального случайного графа // ДАН. 2019. Т. 484. № 5. С. 519-522.
  6. 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.
  7. Bollobás B., Erdős P. Cliques in Random Graphs // Math. Proc. Camb. Phil. Soc. 1976. V. 80. P. 419-427.
  8. Grimmett G.R., McDiarmid C.J.H. On colouring random graphs // Math. Proc. Camb. Phil. Soc. 1975. V. 77. № 2. P. 313-324.
  9. Matula D. The Employee Party Problem // Not. Amer. Math. Soc. 1972. V. 19. № 2. P. A-382.
  10. Matula D. The Largest Clique Size in a Random Graph. Tech. Rep. Dept. Comp. Sci., Southern Methodist University, Dallas, Texas; 1976.
  11. 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.
  12. Райгородский А.М. Об устойчивости числа независимости случайного подграфа // ДАН. 2017. Т. 477. № 6. С. 649-651.
  13. Fountoulakis N., Kang R.J., McDiarmid C. Largest Sparse Subgraphs of Random Graphs // European J. Combinatorics. 2014. V. 35. P. 232-244.
  14. Bollobás B. The Distribution of the Maximum Degree of a Random Graph // Discrete Mathematics. 1980. V. 32. P. 201-203.

Statistics

Views

Abstract - 142

PDF (Russian) - 79

PlumX


Copyright (c) 2019 Russian academy of sciences

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies