Counting oriented trees in digraphs with large minimum semidegree

Abstract

Let $T$ be an oriented tree on $n$ vertices with maximum degree at most $e^{o(\sqrt{\log n})}$. If $G$ is a digraph on $n$ vertices with minimum semidegree ${\delta }^0(G)\ge (\frac{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}(\frac{1}{2}-o(1){)}^{n}n!$ copies of $T$, which is optimal. This implies the analogous result in the undirected case.

arXiv comment24 pages