Linear minimum-out-degree conjecture for transitive tournament immersions

From papers

Let DD be a digraph, let kk be a positive integer, and write δ+(D)\delta^{+}(D) for its minimum out-degree. A transitive tournament on kk 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 C>0C>0 such that, for every positive integer kk, every digraph DD satisfying

δ+(D)Ck\delta^{+}(D)\geq Ck

contains an immersion of a transitive tournament on kk vertices. Lochet proved the analogous assertion with an unspecified function of kk, 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

No solutions have been posted yet.