Hamilton powers conjecture for inhomogeneous random graphs

From papers

Let W:Ω2[0,1]W:\Omega^2\to[0,1] be a graphon, let k2k\ge 2 be fixed, and let G(n,W)\mathbb{G}(n,W) be the associated inhomogeneous random graph. A Kk+1K_{k+1}-fractional cover of WW is a measurable function f:Ω[0,1]f:\Omega\to[0,1] such that for almost every (k+1)(k+1)-tuple (x1,,xk+1)(x_1,\ldots,x_{k+1}), either i=1k+1f(xi)1\sum_{i=1}^{k+1}f(x_i)\ge1 or at least one pair among the tuple has graphon value zero. Hamilton-power conjecture. The graph G(n,W)\mathbb{G}(n,W) contains asymptotically almost surely the kk-th power of a Hamilton cycle if and only if: WW is a connected graphon; limα0μ(Dα(W))/α=0\lim_{\alpha\searrow0}\mu(\mathsf{D}_\alpha(W))/\alpha=0; and the only Kk+1K_{k+1}-fractional cover of WW with L1L^1-norm at most 1/(k+1)1/(k+1) is the constant function 1/(k+1)1/(k+1). The conjecture extends the Hamilton-cycle characterization to higher powers, replacing the perfect-matching obstruction by the corresponding Kk+1K_{k+1}-tiling obstruction.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Frederik Garbe, Jan Hladký and Simón Piga, “Hamiltonicity of inhomogeneous random graphs”, arXiv:2604.00899 (2026).

Solutions 0

No solutions have been posted yet.