Counting oriented trees in digraphs with large minimum semidegree.

Let T be an oriented tree on n vertices with maximum degree at most e o (log ⁡ n). If G is a digraph on n vertices with minimum semidegree δ 0 (G) ≥ (1 2 + o (1)) n , then G contains T as a spanning tree, as recently shown by Kathapurkar and Montgomery (in fact, they only require maximum degree o (n / log ⁡ n)). This generalizes the corresponding result by Komlós, Sárközy and Szemerédi for graphs. We investigate the natural question how many copies of T the digraph G contains. Our main result states that every such G contains at least | Aut (T) | − 1 (1 2 − o (1)) n n ! copies of T , which is optimal. This implies the analogous result in the undirected case. [ABSTRACT FROM AUTHOR]