A scaling limit for the length of the longest cycle in a sparse random\n graph

2019/07/08 by Michael Anastos, Alan Frieze, Anastos, Michael +1 · 1 citation
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Geometry and complex manifolds #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1907.03657

Abstract

We discuss the length of the longest cycle in a sparse random graph\nG_n,p,p=c/n. c constant. We show that for large c there is a function\nf(c) such that L_n(c)/n\→ f(c) a.s. The function f(c)=1-\∑_k=1^\∞\np_k(c)e^-kc where p_k is a polynomial in k. We are only able to\nexplicitly give the values p₁,p₂, although we could in principle compute\nany p_k. We see immediately that the length of the longest path is also\nasymptotic to f(c)n w.h.p.\n

Cited by

• Finding Planted Cycles in a Random Graph

Related

• A scaling limit for the length of the longest cycle in a sparse random digraph
• A note on long cycles in sparse random graphs
• Cycle lengths in sparse random graphs
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• The law of the circumference of sparse binomial random graphs