pith. machine review for the scientific record. sign in

arxiv: 1408.4332 · v1 · submitted 2014-08-19 · 🧮 math.CO

Recognition: unknown

The threshold probability for long cycles

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphprobabilitycycleleastomegarandomthresholdalmost
0
0 comments X
read the original abstract

For a given graph $G$ of minimum degree at least $k$, let $G_p$ denote the random spanning subgraph of $G$ obtained by retaining each edge independently with probability $p=p(k)$. We prove that if $p \ge \frac{\log k + \log \log k + \omega_k(1)}{k}$, where $\omega_k(1)$ is any function tending to infinity with $k$, then $G_p$ asymptotically almost surely contains a cycle of length at least $k+1$. When we take $G$ to be the complete graph on $k+1$ vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.

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.