A note on long cycles in sparse random graphs

DOI10.37236/11471MaRDI QIDQ6042104zbMATH OpenFDO

Authors Michael Anastos

Publication date 16 May 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2105.13828

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

longest cyclescaling limitsparse random graphweakly pancyclic graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

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}/nof(c)$ a.s. for $cgeq20$, thus extending a result of the author and Frieze to smaller values of $c$. Thereafter, for $cgeq20$, 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 $noinfty$.

Review text

Summary: 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 \to f(c)\) a.s. for \(c\geqslant 20\), thus extending a result of \textit{M. Anastos} and \textit{A. Frieze} [J. Comb. Theory, Ser. B 148, 184--208 (2021; Zbl 1459.05059)] to smaller values of \(c\). Thereafter, for \(c\geqslant 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\to \infty \).

Recommendations

• A scaling limit for the length of the longest cycle in a sparse random graph
• scientific article; zbMATH DE number 3916307
• Cycle lengths in sparse random graphs
• The size of the largest hole in a random graph
• A scaling limit for the length of the longest cycle in a sparse random digraph

Cites work

• A scaling limit for the length of the longest cycle in a sparse random digraph
• A scaling limit for the length of the longest cycle in a sparse random graph
• A sufficient condition for all short cycles
• Cycle lengths in sparse random graphs
• Cycles in a random graph near the critical point
• Hamiltonian cycles in random regular graphs
• scientific article; zbMATH DE number 3865331 (Why is no real title available?)
• scientific article; zbMATH DE number 3916307 (Why is no real title available?)
• scientific article; zbMATH DE number 3693325 (Why is no real title available?)
• scientific article; zbMATH DE number 17673 (Why is no real title available?)
• scientific article; zbMATH DE number 3540832 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Introduction to Random Graphs
• Long paths in sparse random graphs
• On large matchings and cycles in sparse random graphs
• On the method of typical bounded differences
• On the number of circuits in random graphs
• Pancyclic graphs. I
• Random graphs.
• Sudden emergence of a giant k-core in a random graph
• The longest path in a random graph

Cited in

(14)

• On large matchings and cycles in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• Longest cycles in sparse random digraphs
• scientific article; zbMATH DE number 3916307 (Why is no real title available?)
• scientific article; zbMATH DE number 1335045 (Why is no real title available?)
• An improved upper bound on the length of the longest cycle of a supercritical random graph
• On the spectra of large sparse graphs with cycles
• Cycle lengths in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random digraph
• The emergence of a giant rainbow component
• The completion numbers of Hamiltonicity and pancyclicity in random graphs
• Constructing Hamilton cycles and perfect matchings efficiently (extended abstract)
• Finding planted cycles in a random graph
• A short proof of a central limit theorem for the order of the giant component and k-core

This page was built for publication: A note on long cycles in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6042104)