Subdivisions of transitive tournaments (Q1590220): Difference between revisions

A subdivision of a digraph is a digraph obtained by replacing arcs by directed paths (in the same direction as the arcs). It is proved that, for \(r\geq 2\) and \(n\geq n(r)\), every digraph with \(n\) vertices and more arcs than the \(r\)-partite Turán graph \(T(r,n)\), contains a subdivision of the transitive tournament on \(r+1\) vertices. Moreover, the extremal digraphs are the orientations of \(T(r,n)\) induced by orderings of the vertex classes.