Cycle Saturation in Random Graphs

Yury Demidovich*, Maksim Zhukovskii

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


For a fixed graph F, the minimum number of edges in an edge-maximal F-free subgraph of G is called the F-saturation number. The asymptotics of the F-saturation number of the Erdös–Rényi random graph G(n, p) for constant p∈ (0, 1 ) was established for any complete graph and any star graph. We obtain the asymptotics of the Cm -saturation number of G(n, p) for m⩾ 5. Also we prove non-trivial linear (in n) lower bounds and upper bounds for the C4 -saturation number of G(n, p) for some fixed values of p.

Original languageEnglish (US)
Title of host publicationTrends in Mathematics
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages6
StatePublished - 2021

Publication series

NameTrends in Mathematics
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X

Bibliographical note

Funding Information:
Acknowledgements. This work was carried out with the financial support of the Ministry of Education and Science of the Russian Federation, in the framework of Megagrant no. 075-15-2019-1926. The work of the first author was also supported by the Simons Foundation.

Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.


  • Cycle
  • Extremal graph theory
  • Random graph
  • Saturation

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Cycle Saturation in Random Graphs'. Together they form a unique fingerprint.

Cite this