Erdős Problem #71 — Cycles in Prescribed Arithmetic Progressions

This asks whether sufficiently large average degree forces a cycle length in every prescribed infinite arithmetic progression containing an even integer. It is the Erdős–Burr cycle-length conjecture in this formulation.

Known results

• Erdős and Burr settled the case $k=2$.
• Robertson settled the case $k=0$.
• Bollobás resolved the full odd-modulus conjecture; the 2002 paper proves that average degree at least $8k$ suffices for every residue modulo odd $k$.
• Thomassen’s 1983 even-modulus results, later confirmed in the cited work, give cycles of all even lengths modulo even $k$ under minimum degree at least $k+1$; a sufficiently large average degree yields the required subgraph.

Current status (as of February 2026): Resolved: odd common differences follow from Bollobás’s theorem, and even common differences from Thomassen’s even-modulus theorem together with the standard average-degree reduction.