pith. sign in

arxiv: 2502.14515 · v1 · pith:H5DKE5T3new · submitted 2025-02-20 · 🧮 math.CO

Sharp thresholds for higher powers of Hamilton cycles in random graphs

classification 🧮 math.CO
keywords subgraphsthresholdhamiltonmethodmomentproofquantitiesrandom
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Spanning triangulations in random graphs

    math.CO 2026-05 unverdicted novelty 6.0

    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.