Strongly negative cases for Hamiltonicity in graphon random graphs
Strongly negative cases for Hamiltonicity in graphon random graphs
Let be a graphon, and let denote the associated inhomogeneous random graph. The four conditions in Proposition~ are: is not a connected graphon; ; has a narrow peninsula; or there is a partition with such that is zero almost everywhere on . Completeness conjecture. If satisfies none of these four conditions, then
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
Sign in to submit a solution.
No solutions have been posted yet.