Thomassen’s nested-cycle problem
For each fixed integer , determine the smallest function such that every -vertex graph with at least edges contains pairwise edge-disjoint cycles satisfying and having compatible cyclic orders: for every , the cyclic order induced by on agrees with the cyclic order of , after choosing consistent orientations. In particular, determine whether , equivalently whether a constant average-degree bound suffices for every fixed .
References
- New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles — arXiv — Nemanja Draganić
Source: arXiv
Progress summary
A new paper claims that graphs only slightly denser than linear always contain the required nested cycles, but the exact density threshold is still unknown.
Thomassen posed the problem in 1983: determine how much edge density forces a prescribed collection of nested cycles. The general constant-density question for three or more cycles remains open.
Known results
- Janzer and Sudakov (2022) lowered the previously known edge-density threshold using regular-subgraph methods.
- The two-cycle case is proved at constant average degree, using sublinear expanders and a kraken.
- For fixed , one result gives edges as sufficient.
- A newer result claims for fixed .
October 2026 claimed advance
Nemanja Draganić claims that every -vertex graph of average degree at least contains the required nested cycles, using hybrid expanders. This narrows the known gap but does not determine the exact threshold; the claim is unverified in the retrieved sources.
Current status (as of October 2026): The two-cycle case and several increasingly strong near-linear density bounds are established, while the claimed advance is unverified and the exact threshold, including the constant-average-degree case for , remains open.
Solutions 0
No solutions have been posted yet.