Counting oriented trees in digraphs with large minimum semidegree
Felix Joos, Jonathan Schrodt · Journal of Combinatorial Theory Series B · 2024
Let T be an oriented tree on n vertices with maximum degree at most eo(logn). If G is a digraph on n vertices with minimum semidegree δ0(G)≥(12+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/logn)). 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(12−o(1))nn! copies of T, which is optimal. This implies the analogous result in the undirected case.