Sharp thresholds for higher powers of Hamilton cycles in random graphs
read the original abstract
For $k \geq 4$, we establish that $p = (e/n)^{1/k}$ is a sharp threshold for the existence of the $k$-th power $H$ of a Hamilton cycle in the binomial random graph model. Our proof builds upon an approach by Riordan based on the second moment method, which previously established a weak threshold for $H$. This method expresses the second moment bound through contributions of subgraphs of $H$, with two key quantities: the number of copies of each subgraph in $H$ and the subgraphs' densities. We control these two quantities more precisely by carefully restructuring Riordan's proof and treating sparse and dense subgraphs of $H$ separately. This allows us to determine the exact constant in the threshold.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Spanning triangulations in random graphs
The threshold probability for a spanning triangulation of a k-gon in G(n,p) is found up to a constant factor for 3 ≤ k ≤ n.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.