# zbMATH — the first resource for mathematics

Highly linked tournaments. (English) Zbl 1319.05063
Summary: A (possibly directed) graph is $$k$$-linked if for any two disjoint sets of vertices $$\{x_1,\dots,x_k\}$$ and $$\{y_1,\dots,y_k\}$$ there are vertex disjoint paths $$P_1,\dots,P_k$$ such that $$P_i$$ goes from $$x_i$$ to $$y_i$$. A theorem of B. Bollobás and A. Thomason [Combinatorica 16, No. 3, 313–320 (1996; Zbl 0870.05044)] says that every 22$$k$$-connected (undirected) graph is $$k$$-linked. It is desirable to obtain analogues for directed graphs as well. Although C. Thomassen [“Note on highly connected non-2-linked digraphs”, Combinatorica 11, No. 3, 393–395 (1991)] showed that the Bollobás-Thomason theorem does not hold for general directed graphs, he [“Connectivity in tournaments”, in: B. Bollobás (ed.), Graph theory and combinatorics. Proceedings of the Cambridge combinatorial conference, in honour of Paul Erdős. London: Academic Press. 305–313 (1984)] proved an analogue of the theorem for tournaments – there is a function $$f(k)$$ such that every strongly $$f(k)$$-connected tournament is $$k$$-linked. The bound on $$f(k)$$ was reduced to $$O(k\log k)$$ by D. Kühn et al. [Proc. Lond. Math. Soc. (3) 109, No. 3, 733–762 (2014; Zbl 1302.05069)], who also conjectured that a linear bound should hold. We prove this conjecture, by showing that every strongly $$452k$$-connected tournament is $$k$$-linked.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C40 Connectivity
##### Keywords:
 [1] Ajtai, M.; Komlós, J.; Szemerédi, E., Sorting in $$c \log n$$ parallel steps, Combinatorica, 3, 1-19, (1983) · Zbl 0523.68048 [2] Bang-Jensen, J., On the 2-linkage problem for semicomplete digraphs, Ann. Discrete Math., 41, 23-38, (1989) · Zbl 0664.05034 [3] Bollobás, B.; Thomason, A., Highly linked graphs, Combinatorica, 16, 313-320, (1996) · Zbl 0870.05044 [4] Jung, H. A., Verallgemeinerung des n-fachen zusammenhangs für graphen, Math. Ann., 187, 95-103, (1970) · Zbl 0184.27601 [5] Kühn, D.; Kim, J.; Osthus, D., Bipartitions of highly connected tournaments, (2014) · Zbl 1346.05094 [6] Kühn, D.; Lapinskas, J.; Osthus, D.; Patel, V., Proof of a conjecture of thomassen on Hamilton cycles in highly connected tournaments, Proc. Lond. Math. Soc., 109, 733-762, (2014) · Zbl 1302.05069 [7] Kühn, D.; Osthus, D.; Townsend, T., Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths, Combinatorica, (2014), in press [8] Larman, D. G.; Mani, P., On the existence of certain configurations within graphs and the 1-skeletons of polytopes, Proc. Lond. Math. Soc., 20, 144-160, (1974) · Zbl 0201.56801 [9] Mader, W., Homomorphieeigenschaften und mittlere kantendichte von graphen, Math. Ann., 174, 265-268, (1967) · Zbl 0171.22405 [10] A. Pokrovskiy, Edge disjoint Hamiltonian cycles in highly connected tournaments, preprint, 2014. [11] Thomas, R.; Wollan, P., An improved extremal function for graph linkages, European J. Combin., 26, 309-324, (2005) · Zbl 1056.05091 [12] Thomassen, C., Connectivity in tournaments, (Bollobás, B., Graph Theory and Combinatorics, a Volume in Honour of Paul Erdős, (1984), Academic Press London), 305-313 [13] Thomassen, C., Note on highly connected non-2-linked digraphs, Combinatorica, 11, 393-395, (1991) · Zbl 0746.05030