Proof of Lichiardopol's conjecture on disjoint directed cycles of distinct lengths

Abstract

There is a fascinating array of interrelated questions studying which structures can be guaranteed in digraphs of large minimum out-degree. These often have intriguingly simple statements, yet seem surprisingly difficult to approach. A well-known example is Lichiardopol's conjecture (2014), stating that there exists a function $g:\mathbb{N}\rightarrow \mathbb{N}$ such that every digraph with minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of distinct lengths. In this paper, building on earlier work of the second author, we confirm this conjecture in full generality. We also generalise this result to a weighted setting. Our proof uses and combines many ingredients from structural digraph theory such as butterfly minors, directed tangles, a directed analogue of the Tangle-Wall Theorem due to Robertson and Seymour as well as a local variant of the Directed Flat Wall Theorem due to Giannopoulou, Kawarabayashi, Kreutzer and Kwon. These techniques, which are somewhat atypical in the study of minimum degree conditions, may be of independent interest and may find further applications.

Disclosure

“ncerning the generation of the mathematical ideas, all of the presented proof ideas are fully due to the authors, with the sole exception of the proof presented in Section 4.2, for which we used assistance from ChatGPT 5.5 Pro. Concretely, ChatGPT suggested to use Theorem 4.6 and Lemma 4.10, and it proved Lemma 4.10. Acknowledgments We dearly thank Dan Král, Filip Kučerák, and Lina Simbaqueba for inspiring and helpful discussions. In particular, we thank Dan Král for asking a goo”

PDF page 24

Classification

Drafting a complete proof for author revision

Multiplier

9

Verified

2026-08-22T18:10:33.392629Z

Structural counts