Linear minimum-out-degree conjecture for transitive tournament immersions
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.