Subdivision of a transitive tournament in digraphs with large outdegree.
A fundamental result of Mader [M1] states that for every integer there is a smallest so that every graph of average degree at least contains a subdivision of a complete graph on vertices. Bollobás and Thomason [BT] as well as Komlós and Szemerédi [KS] showed that is quadratic in .
The above conjecture is a digraph analogue of this result. However one cannot replace the minimum outdegree in this conjecture by the average degree as in Mader's analogue for graphs: consider the complete bipartite graph and orient all edges from the first to the second class. The resulting digraph has average degree but not even a transitive tournament on 3 vertices.
One might be tempted to conjecture that large minimum outdegree would even force the existence of a subdivision of a large complete digraph. However, for all Thomassen [T] constructed a digraph on vertices whose minimum outdegree is at least but which does not contain an even directed cycle (and thus no complete digraph on 3 vertices). A simpler construction was found by DeVos et al. [DMMS].
It is easy to see that and . Mader [M3] showed that . Even the existence of is not known.
Bibliography
[BT] B. Bollobás and A. Thomason, Proof of a conjecture of Mader, Erdös and Hajnal on topological complete subgraphs, European Journal of Combinatorics 19 (1998), 883–887.
[DMMS] M. DeVos, J. McDonald, B. Mohar, and D. Scheide, Immersing complete digraphs, European Journal of Combinatorics, 33 (2012), no 6, 1294-1302.
[KS] J. Komlós and E. Szemerédi, Topological Cliques in Graphs II, Combinatorics, Probability and Computing 5 (1996), 70–90.
[M1] W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Math. Annalen 174 (1967), 265–268.
* [M2] W. Mader, Degree and Local Connectivity in Digraphs, Combinatorica 5 (1985), 161–165.
[M3] W. Mader, On Topological Tournaments of order 4 in Digraphs of Outdegree 3, Journal of Graph Theory 21 (1996), 371–376.
[T] C. Thomassen, Even Cycles in Directed Graphs, European Journal of Combinatorics 6 (1985), 85–89.
* indicates original appearance(s) of problem.