A note on long cycles in sparse random graphs

2021/05/28 by Michael Anastos, Anastos, Michael · 3 citations
Mathematics · #05C38 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2105.13828

openalex publication_date 2021/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let L_c,n denote the size of the longest cycle in G(n,c/n), c>1 constant. We show that there exists a continuous function f(c) such that L_c,n/n → f(c) a.s. for c≥ 20, thus extending a result of the author and Frieze to smaller values of c. Thereafter, for c≥ 20, we determine the limit of the probability that G(n,c/n) contains cycles of every length between the length of its shortest and its longest cycles as n→ ∞.

Cited by

• Finding Planted Cycles in a Random Graph
• Cycle lengths in the percolated hypercube
• A short proof of a central limit theorem for the order of the giant component and k-core

Related

• A scaling limit for the length of the longest cycle in a sparse random\n graph
• Cycle lengths in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random digraph
• An improved lower bound on the length of the longest cycle in random graphs
• Longest cycles in sparse random digraphs