Concentration and separation conjecture for cycle lengths in Hamiltonian graphs

Let GG be an nn-vertex Hamiltonian graph with minimum degree at least 33. Concentration and separation conjecture. Both of the following hold:

  1. GG has Ω(n)\Omega(\sqrt n) cycle lengths all lying in an interval of size O(n)O(\sqrt n).
  2. GG has Ω(n)\Omega(\sqrt n) cycle lengths such that any two are at least Ω(n)\Omega(\sqrt n) apart.

These are proposed intermediate steps toward a linear lower bound on the number of cycle lengths. The source says that the main asymptotic conjecture implies this statement, but does not report a proof of either assertion, so it remains open.

Sources & referencesView supporting material

Primary source

Matija Bucić, Lior Gishboliner and Benny Sudakov, “Cycles of many lengths in Hamiltonian graphs”, arXiv:2104.07633 (2021).

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.