An arXiv preprint reports a proof that a minimum-out-degree condition can guarantee a requested number of vertex-disjoint directed cycles whose lengths are pairwise different. The result establishes an abstract threshold function g: for each prescribed number of cycles, every in-scope digraph meeting the relevant degree threshold contains the required collection.
But the result arrives without a plug-in number. The paper does not compute or optimize g explicitly; it says a computable function could be derived by combining the literature results used in the proof. The theorem therefore supplies an existence guarantee, not the smallest degree a reader would need for a particular request.
The question behind the theorem
The problem is framed as Lichiardopol’s conjecture. It asks whether a minimum-out-degree threshold can guarantee any prescribed number of directed cycles that share no vertices and have pairwise distinct lengths. The introduction reports that the conjecture had remained unresolved even for the case k = 3 before this paper.
The new theorem answers that existence question across the conjecture’s stated range of requested cycle counts. Its conclusion is about whether a suitable threshold exists, rather than about the numerical efficiency of that threshold.
A guarantee about mathematical structures
The scope matters. The objects studied are finite simple digraphs, with anti-parallel edge pairs allowed. In other words, the framework permits directed edges between the same two vertices in opposite directions. The units of analysis are mathematical digraphs and formal constructions, not an empirical population.
For a general reader, minimum out-degree can be understood as a lower bound on how many directed edges leave each vertex. If every vertex in a qualifying digraph meets the relevant bound, the theorem guarantees the requested collection of disjoint cycles with different lengths.
A proof built from structure
The argument uses structural digraph methods rather than statistical analysis. It combines butterfly minors, directed tangles, a directed Tangle-Wall analogue and a local Directed Flat Wall variant. These are the intermediate structures through which the proof studies the shape of a digraph and connects its degree condition to the required cycle packing.
The verified analysis describes the overall strategy as a formal proof by contradiction supported by induction on a minimal counterexample. That approach lets the argument assume that a smallest failure exists and then use the structural results to constrain what such a failure could look like.
One technical step concerns a defined separation set, written as τ. The relevant lemma says that if there are no two disjoint subdigraphs with minimum out-degree at least d/4, then τ is a d/4-tangle. The tangle is a way of recording which side of each permitted separation is selected by the digraph’s structure.
The proof then uses a sufficiently high-order tangle to obtain a cylindrical wall of order 3k − 2. Its rows and columns identify the side selected by the tangle for every separation of order below k. In the larger argument, these structural checkpoints provide the route from local degree information to the collection of cycles promised by the theorem.
The same framework carries weights
The result also has a vertex-weighted consequence. When vertices carry strictly positive weights, the same abstract degree threshold guarantees vertex-disjoint directed cycles whose total vertex weights are pairwise different.
A separate corollary covers edge weights drawn from a finite set. In that setting, a minimum-out-degree threshold scaled by the number of allowed edge-weight values guarantees disjoint cycles with pairwise distinct total edge weights.
What the theorem leaves open
The main unresolved quantitative issue is the function g itself. The paper does not give an explicit optimized formula, and the smallest possible threshold function remains an open problem. A sharper bound would show how much minimum out-degree is actually necessary for each requested number of cycles.
The edge-weighted conclusion also has a clear boundary: it applies when the edge weights come from a finite set. It does not establish the same result for unrestricted positive edge weights. That restriction is part of the theorem’s formal scope, not a detail that can be dropped from the statement.
Because this is a formal proof about digraphs, it does not provide an empirical effect estimate, statistical uncertainty or a replication sample. Its output is a mathematical guarantee within the stated class of finite simple digraphs.
Preprint status and disclosure
The supplied front matter identifies the work as an arXiv preprint, version 1, dated 20 August 2026. No journal publication is reported in the metadata. The paper reports support from the Alexander von Humboldt Foundation and the SNSF Ambizione Grant No. 216071 of the Swiss National Science Foundation.
An author disclosure says that humans wrote the paper and that ChatGPT 5.5 Pro assisted with one proof section by suggesting two cited ingredients and proving a lemma.
The preprint therefore establishes the existence of the threshold guarantee while leaving its sharp quantitative form open. The questions that follow are whether the existential threshold can be replaced by a sharper explicit bound and whether the structural methods can yield further cycle-packing or weighted results.
Paper data and sources
Original title: Proof of Lichiardopol's conjecture on disjoint directed cycles of distinct lengths
Authors: Sandra Albrechtsen, Raphael Steiner
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text