An improved upper bound on the length of the longest cycle of a supercritical random graph
classification
🧮 math.CO
keywords
upperboundcyclegraphlengthlongestrandomsupercritical
read the original abstract
We improve Luczak's upper bounds on the length of the longest cycle in the random graph G(n,M) in the "supercritical phase" where M=n/2+s and s=o(n) but n^{2/3}=o(s). The new upper bound is (6.958+o(1))s^2/n with probability 1-o(1) as n approaches infinity. Letting c=1+2s/n, the equivalence between G(n,p) and G(n,M) implies the same result for G(n,p) where p=c/n, c approaching 1, c-1 = omega(n^{-1/3}).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.