Spanning trees in dense directed graphs

Abstract: In 2001, Koml'os, S'ark"ozy and Szemer'edi proved that, for each

a l p h a > 0

, there is some

c > 0

and

n_{0}

such that, if

n g e q n_{0}

, then every

n

-vertex graph with minimum degree at least

(1 / 2 + a l p h a) n

contains a copy of every

n

-vertex tree with maximum degree at most

c n / l o g n

. We prove the corresponding result for directed graphs. That is, for each

a l p h a > 0

, there is some

c > 0

and

n_{0}

such that, if

n g e q n_{0}

, then every

n

-vertex directed graph with minimum semi-degree at least

(1 / 2 + a l p h a) n

contains a copy of every

n

-vertex oriented tree whose underlying maximum degree is at most

c n / l o g n

. As with Koml'os, S'ark"ozy and Szemer'edi'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

D e l t a

, for any constant

D e l t a i n m a t h b b N

and sufficiently large

n

. In contrast to these results, our methods do not use Szemer'edi's regularity lemma.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Spanning trees in dense directed graphs