Linear minimum-out-degree conjecture for transitive tournament immersions
Let be a digraph, let be a positive integer, and write for its minimum out-degree. A transitive tournament on vertices is the tournament whose vertices admit an ordering in which every edge points forward; an immersion replaces its directed edges by pairwise edge-disjoint directed paths. Linear out-degree immersion conjecture. There exists an absolute constant such that, for every positive integer , every digraph satisfying
contains an immersion of a transitive tournament on vertices. Lochet proved the analogous assertion with an unspecified function of , while the linear bound for arbitrary digraphs remains open.
References
Primary source
António Girão and Robert Hancock, “Immersions of directed graphs in tournaments”, arXiv:2305.06204 (2024).
Additional references
3 papers in this index state this conjecture (2019–2023). The statement above is taken from the most recent of them; the others are arXiv:2108.13959, arXiv:1912.00710.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.