Krivelevich–Sudakov Hamiltonicity conjecture for pseudorandom graphs

Let GG be an (n,d,λ)(n,d,\lambda)-graph, meaning an nn-vertex dd-regular graph whose non-trivial eigenvalues have absolute value at most λ\lambda. A Hamilton cycle is a cycle containing every vertex of GG. Krivelevich and Sudakov's conjecture. There exists a positive constant CC such that, if

dλC,\frac{d}{\lambda}\ge C,

then GG 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

Never refreshed

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

Solutions 0

No solutions have been posted yet.