Strongly negative cases for Hamiltonicity in graphon random graphs

From papers

Let W:Ω2[0,1]W:\Omega^2\to[0,1] be a graphon, and let G(n,W)\mathbb{G}(n,W) denote the associated inhomogeneous random graph. The four conditions in Proposition~ are: WW is not a connected graphon; limα0μ(Dα(W))/α=\lim_{\alpha\searrow 0}\mu(\mathsf{D}_\alpha(W))/\alpha=\infty; WW has a narrow peninsula; or there is a partition Ω=ST\Omega=S\sqcup T with μ(S)=μ(T)=1/2\mu(S)=\mu(T)=1/2 such that WW is zero almost everywhere on (S×S)(T×T)(S\times S)\cup(T\times T). Completeness conjecture. If WW satisfies none of these four conditions, then

lim supnP[G(n,W) is Hamiltonian]>0.\limsup_{n\to\infty}\mathbf{P}[\mathbb{G}(n,W)\text{ is Hamiltonian}]>0.

The conjecture asserts that these are exactly the strongly negative graphon obstructions, complementing the theorem that each listed condition makes Hamiltonicity asymptotically almost impossible. Its resolution would characterize when Hamiltonicity has probability bounded away from zero rather than tending to zero.

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.