Counting oriented trees in digraphs with large minimum semidegree - Joos, Felix; Schrodt, Jonathan (Journal of combinatorial theory, 2024)
Let T be an oriented tree on n vertices with maximum degree at most eo(log⁡n). 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/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(12−o(1))nn! copies of T, which is optimal. This implies the analogous result in the undirected case.
Online verfügbar: 29. Mai 2024
Gesehen am 14.11.2024