Cycle lengths in sparse random graphs

Yahav Alon, Michael Krivelevich, Eyal Lubetzky

Research output: Contribution to journalArticlepeer-review

Abstract

We study the set (Formula presented.) of lengths of all cycles that appear in a random d-regular graph G on n vertices for (Formula presented.) fixed, as well as in binomial random graphs on n vertices with a fixed average degree (Formula presented.). Fundamental results on the distribution of cycle counts in these models were established in the 1980s and early 1990s, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in n. Here we derive, for a random d-regular graph, the limiting probability that (Formula presented.) simultaneously contains the entire range (Formula presented.) for (Formula presented.), as an explicit expression (Formula presented.) which goes to 1 as (Formula presented.). For the random graph (Formula presented.) with (Formula presented.), where (Formula presented.) for some absolute constant (Formula presented.), we show the analogous result for the range (Formula presented.), where (Formula presented.) is the length of a longest cycle in G. The limiting probability for (Formula presented.) coincides with (Formula presented.) from the d-regular case when c is the integer (Formula presented.). In addition, for the directed random graph (Formula presented.) we show results analogous to those on (Formula presented.), and for both models we find an interval of (Formula presented.) consecutive cycle lengths in the slightly supercritical regime (Formula presented.).

Original languageEnglish (US)
JournalRandom Structures and Algorithms
DOIs
StateAccepted/In press - 2021

Keywords

  • cycle lengths
  • regular graphs
  • sparse random graphs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Cycle lengths in sparse random graphs'. Together they form a unique fingerprint.

Cite this