Reproduce “A relaxation of the Bermond-Thomassen conjecture” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni, Raphael Steiner, Sebastian Wiederrecht
The research demonstrates that any digraph with a minimum out-degree of at least 2k-1 contains k vertex-disjoint cycles that are either directed or become directed by reversing a single arc. This finding establishes a sharp minimum out-degree bound for this relaxed cycle packing problem, addressing an open question in graph theory.
Key insights
- By relaxing the cycle definition to 'near-directed cycles' (allowing one arc reversal to make it directed) while preserving the original 2k-1 minimum out-degree condition, the work explores a different facet of the Bermond-Thomassen conjecture.
- The proof hinges on selecting an extremal collection of k-1 vertex-disjoint near-directed cycles that minimizes covered vertices and maximizes the longest directed path in the remaining subgraph, allowing for precise structural analysis.
- Detailed analysis of out-degree properties and interconnections between the remaining path and the selected cycles, utilizing a series of averaging arguments and forbidden configurations, is crucial to deriving the final contradiction.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.