Krivelevich–Sudakov Hamiltonicity conjecture for pseudorandom graphs
Krivelevich–Sudakov Hamiltonicity conjecture for pseudorandom graphs
Let be an -graph, meaning an -vertex -regular graph whose non-trivial eigenvalues have absolute value at most . A Hamilton cycle is a cycle containing every vertex of . Krivelevich and Sudakov's conjecture. There exists a positive constant such that, if
then contains a Hamilton cycle.
This conjecture asks for a spectral-gap condition guaranteeing Hamiltonicity in pseudorandom graphs. The paper presents it as a conjecture posed nearly 20 years ago; no resolution is supplied in the provided context.
Sources & referencesView supporting material
Primary source
Matías Pavez-Signé, “Spanning trees in the square of pseudorandom graphs”, arXiv:2307.00322 (2023).
Additional references
2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2205.15228.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.