The linear connectivity conjecture for linked tournaments

A tournament is an orientation of a complete graph. A tournament is strongly rr-connected when deleting fewer than rr vertices leaves a strongly connected digraph. A tournament is kk-linked if, for every choice of kk distinct initial vertices and kk distinct terminal vertices, there are kk vertex-disjoint directed paths linking the prescribed pairs.

Linear connectivity conjecture for linked tournaments. There exists a constant C>0C>0 such that, for every kNk\in\mathbb{N}, every strongly CkCk-connected tournament is kk-linked.

The paper proves a near-linear bound, namely strong 104klogk10^4k\log k-connectivity implies kk-linkedness, and notes that removing the logarithmic factor remains conjectural.

Sources & referencesView supporting material

Primary source

Daniela Kühn, John Lapinskas, Deryk Osthus and Viresh Patel, “Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments”, arXiv:1303.4213 (2013).

Progress summary

Never refreshed

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.