2020/12/16 by Richard Mycroft, Mycroft, Richard, Tássio Naia +1 · 1 citation
#05C20 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2012.09201
We prove that every oriented tree on n vertices with bounded maximum degree appears as a spanning subdigraph of every directed graph on n vertices with minimum semidegree at least n/2+o(n). This can be seen as a directed graph analogue of a well-known theorem of Komlós, Sárközy and Szemerédi. Our result for trees follows from a more general result, allowing the embedding of arbitrary orientations of a much wider class of spanning "tree-like" structures, such as a collection of at most o(n1/4) vertex-disjoint cycles and subdivisions of graphs H with |H|< n^(log n)-1/2 in which each edge is subdivided at least once.