← All problems

Thomassen’s nested-cycle problem

For each fixed integer k≥3k\ge 3, determine the smallest function fk(n)f_k(n) such that every nn-vertex graph with at least fk(n)f_k(n) edges contains kk pairwise edge-disjoint cycles C1,…,CkC_1,\ldots,C_k satisfying V(C1)⊆⋯⊆V(Ck)V(C_1)\subseteq\cdots\subseteq V(C_k) and having compatible cyclic orders: for every i<ji<j, the cyclic order induced by CjC_j on V(Ci)V(C_i) agrees with the cyclic order of CiC_i, after choosing consistent orientations. In particular, determine whether fk(n)=Ok(n)f_k(n)=O_k(n), equivalently whether a constant average-degree bound suffices for every fixed kk.

References

Progress summary

Refreshed
Open · progress reported

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 k≥3k\geq 3, one result gives Ckn(log⁡n)k−1(log⁡log⁡n)k−3C_k n(\log n)^{k-1}(\log\log n)^{k-3} edges as sufficient.
  • A newer result claims fk(n)=Ok ⁣(n(log⁡log⁡n)2/log⁡log⁡log⁡n)f_k(n)=O_k\!\left(n(\log\log n)^2/\log\log\log n\right) for fixed k≥3k\geq 3.

October 2026 claimed advance

Nemanja Draganić claims that every nn-vertex graph of average degree at least 2ω(log⁡∗n)2^{\omega(\log^* n)} 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 2ω(log⁡∗n)2^{\omega(\log^* n)} advance is unverified and the exact threshold, including the constant-average-degree case for k≥3k\geq 3, remains open.

Sources

Solutions 0

No solutions have been posted yet.