An improved lower bound on the length of the longest cycle in random graphs

2022/08/14 by Michael Anastos, Anastos, Michael
Mathematics · #05C38 #05C80 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2208.06851

openalex publication_date 2022/08/14 · openalex created_date 2022/08/17 · openalex updated_date 2026/07/28

Abstract

We provide a new lower bound on the length of the longest cycle of the binomial random graph G(n,(1+ε)/n) that holds w.h.p. for all ε=ε(n) such that ε³n→ ∞. In the case ε≤ ε₀ for some sufficiently small constant ε₀, this bound is equal to 1.581ε²n which improves upon the current best lower bound of 4ε²n/3 due to Luczak.

Related

• An improved upper bound on the length of the longest cycle of a supercritical random graph
• A note on long cycles in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random\n graph
• Cycle lengths in sparse random graphs
• Long paths and cycles in random subgraphs of graphs with large minimum degree