Spanning trees in dense directed graphs

In 2001, Komlos, Sarkozy and Szemeredi proved that, for each alpha > 0, there is some c > 0 and n(0) such that, if n >= n(0), then every n-vertex graph with minimum degree at least (1/2 +alpha)n contains a copy of every n-vertex tree with maximum degree at most cn/ log n. We prove the corresponding result for directed graphs. That is, for each alpha > 0, there is some c > 0 and n0 such that, if n >= n(0), then every n-vertex directed graph with minimum semi-degree at least (1/2 + alpha)n contains a copy of every n-vertex oriented tree whose underlying maximum degree is at most cn/log n. As with Komlos, Sarkozy and Szemeredi's theorem, this is tight up to the value of c. Our result improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most delta, for any constant delta is an element of N and sufficiently large n. In contrast to these results, our methods do not use Szemeredi's regularity lemma. (C) 2022 Elsevier Inc.

Automated summary

The study proves that for every given alpha value, there exists an appropriate c value and n(0) such that when the size of the graph is greater than or equal to n(0), the directed graph with a minimum semi-degree of at least (1/2 + alpha)n contains a copy of every oriented tree with a maximum degree of at most cn/log n. This result improves previous research and does not use specific regularity lemma.