The linear connectivity conjecture for linked tournaments
The linear connectivity conjecture for linked tournaments
A tournament is an orientation of a complete graph. A tournament is strongly -connected when deleting fewer than vertices leaves a strongly connected digraph. A tournament is -linked if, for every choice of distinct initial vertices and distinct terminal vertices, there are vertex-disjoint directed paths linking the prescribed pairs.
Linear connectivity conjecture for linked tournaments. There exists a constant such that, for every , every strongly -connected tournament is -linked.
The paper proves a near-linear bound, namely strong -connectivity implies -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.